From http://www.benedelman.org/news/012610-1.html

Even if you disable the Google toolbar, it will continue to track your searches/pages viewed if you EVER had the enhanced features turned on.

Another way how Google personalized search results can be shown even if you think you've turned off any way for Google to track you.