This isn't about advertising - you can still advertise just fine, even more so on a search engine where the benefit of tracking is limited as the user explicitly tells you what they're searching for.
Aside, wonder how good/bad ip+agent fingerprinting could be combined with a url that feeds a small randomly generated string with a VERY long cache expiration, with server/proxy no-cache headers (e-tag per agent/ip). Effectively similar to a cookie, without technically being a cookie.
/sarc