I presume you aren't aware of that huge leak of search information by AOL, where people's names, addresses, social security numbers, Disney fetishes, mold fetishes, and plans to kill their wives were revealed to all.
It's only their searches that were revealed. So yeah. If they put in their social security number, names, and addresses -- then it's all there, sure. You're referring to the 2006 'scandal' right? 650,000 different users and their searches over a three month period.
The only information logged is what they searched for, and the ID that searched it. Sure, it's possible to glean names, addresses, and social security numbers from what they search, but it requires at the very least some thought and effort behind it. It's not something bots would easily be able to do, and with 20,000,000 results, doing it by hand is ridiculous.
Besides, do you know how many people type in their name, or address, or friend's name, or phone number, or email address, into a search engine, every single day? There's so many there's no point in counting.
I'm saying that with such a large amount of data, it's pointless to really give a damn about it. Maybe someone can figure out your name and address? So what? They can find a million other people's names and addresses in a second. What are they going to do? The internet isn't filled with serial killers who are going to chase you down and kill you because they can figure out where you live.
Identity theft might be a bigger issue in the US -- is someone's social security number and name/address all you need? If so, why the hell do you type your social security number into a search engine? That's worse than typing your credit card into a search engine, really, and anyone who does either is deserving of whatever happens to them.
This entire thing is ridiculously overblown.