I don't think there's an element of permanence to this, not if Google acts on commonsense logic, anyway. They can expect a ton of legal trouble and bad press (although whether they actually care anymore is moot...
) if deleted search history data persists within their organization. If they have something in the TOS that allows them to do that, wow!... guess even the more paranoid among us are no match for their evil!
I don't trust Google but my instinct tells me they're not that stupid (the Google desktop UI notwithstanding) or evil (getting less confident about that by the minute, TBH, so just hitting post before I have to completely rewrite this.)
My understanding is, this is to avoid the element of surprise/horror that the cross-pollination could result in.