Summary: When you visit the Google search engine and start typing, you'll likely see a dropdown list of search terms. Those might be history, or something else.
I've done everything mentioned in your article to clear my search history, and yet when I visit Google and start typing something to search for I still get a history list underneath what I'm typing. How do I make that stop once and for all?
•
You're not a alone, I get this a lot. The problem isn't so much about clearing history, as it is a misunderstanding.
I'm guessing that you're not seeing history at all. What you're seeing instead is Google trying to be helpful.
•
Here's an example:

I've typed "lsass", and you can see that there's a drop down list of additional terms underneath what I've typed so far. As I type, that list changes, much like a history list might.
Except it's not history.
What's happening here is that as you type Google is making suggestions on popular search terms that match what you've typed so far. This has nothing to do with your previous searches or your history. This is simply Google saying "hey, you've typed XXXX so far, and here are the most popular search terms that also begin with XXXX".
Why? So you can just click on the suggestions rather than having to type them out. Or maybe you'll see something that's actually a better representation of what you're looking for. Or perhaps you'll note that there are lots of results for one term and not another, and decide to search for that instead.
It's just Google trying to be helpful.
And, in very Google-like fashion, you can turn it off if you don't like it.
Next to the search box you've been typing click the link labeled "Preferences".
On the resulting page, scroll down until you see the "Query Suggestions" option:

To turn it off, simply click on the "Do not ..." option, and then click on the Save Preferences button further down the page.
Note: this is a per-machine setting, and it's most likely stored in a cookie. Don't be surprised to see it come back as you move from machine to machine, or if you periodically clean out your cookies.
Related:
How do I delete history items from my Google tool bar? Deleting Google history takes a few steps, depending on what Google history you mean. Here are step-by-step instructions for deleting Google history.
How do I clear my search history in FireFox? Sometimes you just want to clear the things you've searched for from automatically appearing in the browser. These steps clear that information in FireFox.
How do I delete items from Internet Explorer's auto-complete list? Internet Explorer tries to be helpful by showing you recently visited URLs so you don't have to retype them. But what if you don't want them to show?
Article C3616 - January 10, 2009
To clear the search history in Firefox, click the downward arrow within the white box that you type in and you will see your history listed and in the bottom right hand corner is a clickable link that says "Clear search history".
Posted by: Kitty Ashenbrenner at January 13, 2009 2:01 PMIn Firefox 3, next to the actual white box that you type in, is the a little "g" followed by the word "Search" then a tiny downward arrow. Click on the arrow and scroll to the bottom and select "manage", then on the window that opens, choose the "search" tab and uncheck the box next to "Save search history on my computer".
In gmail account, under settings > accounts > Google Account settings > Web History there is a list of every page you opened from google and everything you searched for from google while you were logged in with your gmail account. (This list doesn't get deleted when you clear your browser cache.
14-Jan-2009
If you don't see the effects of Query Suggestions, it likely means you don't have Google Toolbar 5. Earlier Toolbar versions do not have this feature.
Posted by: Arthur at January 13, 2009 5:19 PMTools-Internet Options-Delete-Delete Forms.
Posted by: Barry Sparks at January 13, 2009 7:35 PMSearch history is deleted.
Leo,
If you clear out cookies, you'll be constantly reactivating the option. I have a Google shortcut that I use in SeaMonkey and I modified the URL thus:
http://www.google.com/webhp?complete=0
Much simpler and doesn't depend on a cookie.
Tom -- Vista, CA -- USA
Posted by: Tom at January 14, 2009 4:48 AMFor Firefox with Google toolbar:
Right click in toolbar space. Find options at bottom of list:
"Clear Search History" - click to clear your personal searches.
"Show Suggestions" - check or uncheck to allow or disallow the drop down lists showing popular Google searches by others,
Posted by: Pollyanna at January 14, 2009 11:12 PMHi, Well, regarding trying to switch off this mythical Query preferences radio button set up in Google Preferences, I dutifully downloaded the Google Toolbar 5 (as suggested above). And Lo and behold... still NO Query Preferences radio buttons in Google Preferences!!! So where do I go from here, anyone? (Leo?)
Posted by: Graham Knott at January 15, 2009 9:56 AMall help is directed at removing history. I need help to save it! I lose it every time I restart or reboot.
Posted by: william w. at January 20, 2009 5:48 AMi accidentally deleted history from google drop down list...is there any way i can get it back? i tried system restore and set my computer to an earlier time ...drop down still blank
Posted by: Anonymous at March 14, 2009 1:25 PMIf it's really a history list underneath what you're typing, try using professional software - History Killer Pro
Posted by: Nietzsche at June 17, 2009 5:48 AM