Going to try Scroogle.org and startpage.com, one thing I noticed is that these both sites use http: so the search queries can still be recorded by the ISP's compared to say https.
The encrypted.google.com (I been using this for some time), will still let google keep logs of your activity for 1.5yr.
The Web History
feature requires you to be signed into Google Account when performing search. With multiple browsers and for general web surfing, I don't want to be signed into Google Account.
I use Private Browsing mode too, but this clears only local (stored on your computer) browsing session information, which an extension/toolbars have full access to and can sell to third parties. I have also enabled the 'Do not track' feature in new IE and Firefox browsers, though I doubt that any company respects this feature at the moment. FCC should include these search giants to respect this feature.
Part 2 (long shot): Is there way (or has anyone successfully done this) to contact these search giants and ask them to delete all search data/logs associated with certain IP?
Some sites (myspace etc) do delete this info when requested.