"History is full of [incidents] where people thought they could anonymize or destroy data, but people find a way to recover it," he says. "You have to be more thorough in their destruction -- you have to eventually destroy the connection between the IP address and the searches."

Plus, Google's move may or may not address backup data, which Sullivan notes is not as easily accessible or altered. And the 18-month window also doesn't address data stored via its Web History feature. That information, Sullivan says, is not being destroyed or anonymized over time. "If you want it wiped out," he says on his blog, "Google says you have to do that separately." On the positive side, Web History lets users know exactly what data pertaining to them is stored, and they can take it into their own hands to delete those histories at any time. The same is true of Yahoo's MyWeb feature, which stores user searches if it's been switched on.

With all the focus on user privacy, the search engine firms say they are taking measures to increase the anonymity of users. Google has said it will build privacy protections into its nonsearch products, including Google Talk's "off the record" feature, as well as Google Desktop's "pause" and "lock search" controls. It has also said it will provide easy-to-understand privacy policies for users on its Web site.

For its part, Microsoft says it's actively engaged with data protection authorities around the world on what user information is collected and for what purposes as well as policies around notice and consent. "There is no universal consensus on the 'right' policies," Burk says. "However, we will continue to be active with privacy advocates and authorities as these decisions are made."

In the end, Sherman says, it's up to individual users to decide whether they trust search engine firms with their personal information. "It's something everyone has to decide -- at what level am I comfortable with the reality of improving my search results vs. my identity being connected with the types of queries I do?" he says. And he's careful to note that the question extends way beyond Google, which in his eyes takes strong measures to secure user data. "When you go to Google, you can't get anywhere near their datacenters," he says. "There are levels of security in the company where few people are cleared to get into areas where people can see personally identifiable information."

But to Templeton, that's not enough. "Even when people try to do a good job, things happen, and data still gets out," he says. "If it's collected and in a place that can be accessed, it can get out."

Furthermore, Sherman points out, it's not just search engines that store personal data. "Your ISP knows more about you than any search engine -- not just what you're searching on but every Web site you've visited," he says. On his blog, Sullivan adds, "Google may be anonymizing its records, but your ISP might not be."