The Article 29 Working Party on EU data protection has recommended that search engine providers should not retain user information for longer than six months.
The group said that search companies must be open about data retention policies, and that all data must be anonymous.
The news will come as a blow to the search firms, which currently keep such information for two years or more and hope to use it in the future to deliver targeted advertising.
"Search engine providers must delete or irreversibly anonymise personal data once it no longer serves the specified and legitimate purpose for which it was collected," the Article 29 Working Party said.
"They must also be capable of justifying the retention and the longevity of cookies deployed at all times.
"The consent of the user must be sought for all planned cross-relation of user data and user profile enrichment exercises.
"Website editor opt-outs must be respected by search engines, and requests from users to update/refresh caches must be complied with immediately."
Some search providers, such as Ixquick.com, already exceed the requirements laid out in the report. The Ixquick engine retains information for just 48 hours and never passes it to third parties, unlike most other search companies.
"All 27 member nations embrace the recommendation of their privacy protection officials that would reduce the retention time to a mere six months for search data," said Alex van Eesteren, vice president of business development at Ixquick.com.
"Since that decision may threaten the 'golden goose' of the broader business of internet advertising, which uses customers' online records to offer personally targeted ads, the big search engines will not be pleased at all."
The findings have drawn a quick response from Google. Peter Fleischer, the firm's global privacy counsel, said in his blog that IP addresses should not be considered as personal information since they cannot be used by search engine providers to identify specific individuals.
"Individualisation of internet users is a logical and beneficial result of the way in which internet technology works," wrote Fleischer.
"Sometimes it is also indispensable in order to comply with legal obligations such as presenting or blocking certain information in certain territories.
"Attempting to impose privacy requirements to situations that do not affect someone's right to privacy will not only hamper technological development, but will entirely contradict the common sense principles on which privacy laws were founded.
"Privacy laws should be about protecting identifiable individuals and their information, not about undermining individualisation."
Do you agree?
Have your say on this article