How to prevent Google aggressively associating my account to my searches? I understand they can access my searches when I'm logged in, and of course know the search terms I use, but how can I prevent them to logging searches to my account when:


I'm not logged in
and in private mode
my account has search history turned off already (updated thanks to Izzy's answer)


I'm on Nexus One with CyanogenMod 7, using stock browser with no patches or add-ons.

Steps to reproduce:


open browser
enable private mode
clear all cookies
search for "asdf unique search"
close tab
clear all cookies/history/cache
exit private mode
close browser
open Google search
type "a"


Expected behaviour: Google knows nothing of my search
What happens: it autocompletes "asdf unique search"

Also, all my Google Accounts on this phone have history.google.com turned off.

Is there any way to stop this happening?
First, you can delete your search history:


  
  Visit your Web History page at https://www.google.com/history or click the gear icon gear icon on the upper right corner of a search results page, and go to Web History.
  Click the gear icon gear icon again on the upper corner of the Web History page, and go to Settings.
  Click the delete all link.
  Click the Delete all button to confirm.
  


Next, you can turn off your Web History completely (same source):


  
  Visit your Web History page at https://www.google.com/history or click the gear icon gear icon on the upper right corner of a search results page, and go to Web History.
  Click the gear icon gear icon again on the upper corner of the Web History page, and go to Settings.
  Click the Turn off button next to "Web History is on." To start keeping track of your web search activity again, click the Turn on button.
  


So now you have deleted all past sources, and prevented new ones from being created. Hopefully.

Further, Turn off search history personalization gives you details on how to opt-out of "Signed in searches" and "Signed out searches". For the latter:


  
  Visit google.com/history/optout when not signed in to a Google Account. (If you see the Google homepage, try visiting the link again.)
  On the resulting page, click Disable customizations based on search activity. (Because this preference is stored in a cookie, it'll affect anyone else who uses the same browser and computer as you).
  


Further readings


HOWTO turn off Google's search-history logging and erase your stored history
How do I view, edit, and disable Google search History?
Defending your secrets from Google's prying eyes: The simple three-step solution that keeps your browsing history private
Google search: "google disable search history" (all the above is from the first results page, btw ;)