For many years privacy advocates have claimed that if users were fully informed and aware of privacy policies then they would vote with their feet. Privacy policies would become part of the free market decision making process, in addition to price, brand, reputation, convenience, etc. It appears this process is actually starting to take place in one industry: search engines. It is likely that they have been the first because of the significant public focus on privacy issues around search over the last few years.
First Google said they would "anonymize" their logs after 18 months, which they later shortened to 9. Yahoo countered with 13 months and has now gone to 90 days. I talked about Google's 18 month policy back in March 2007. In August 2007 I mentioned a CNET Report on privacy ratings for Search engines.
This tit for tat shortening of the identifiable log retention policies suggests that pressure around this issue is meaningful to the search engine giants. What is somewhat less clear is whether the pressure is from the market, or from the media / politicians / government.
It is still the case that the logs are not actually deleted, but rather the source IP address and user ID cookies are stripped out. There is a good Wikipedia article on the scandal around a release of "anonymized" AOL search information, and how it was still possible to identify individual users in the data.