IE (with certain settings on) is sending page data back to Microsoft. If it sends the URL, title and referrer back then the following session is pretty easy to reverse engineer.
It's really just an extension of page rank by seeing what links are being clicked on and not just which links exist. Whether MS should be capturing this data under false pretenses is another issue.
If this is the case, then it's rather easy to stop Microsoft from doing this. Just use POST instead of GET in the search page if you detect the browser is IE8. The referrer will always be the generic http://www.google.com/search with no search term information.
Using POST instead of GET is not a good idea for a search results page. Most likely, the user would have to click through a dialog box ("are you sure you want to resubmit this form") every time the browser back button is used to return to the search results. Even if Google used redirects to circumvent this problem, searches won't be saved in the browser's history, which is a bit inconvenient.
Changing from POST to GET in IE8 would stop Microsoft from mining data in the short term, but would drastically decrease the UX of Google for a large portion of its users who could very easily switch to Bing.
OK, so for IE8 users return a single page AJAX app instead as a variant of what's already done with Instant. Still no referrers but no POST warning messages (which, BTW, have to be one of the most annoying things about ASP.Net web forms - postback was a boneheaded design decision from someone who didn't understand HTTP.)
Topic drift: but I'm convinced that ASP.NET postback was a very deliberate design decision from someone who perfectly understood HTTP - and is intentionally obscuring HTTP in order to keep programmers and implementers ignorant of it and dependent on the Microsoft ecosystem.
