That may clear the history, but the drop-down box (at least in IE) doesn't get cleared with the history. The only way to get rid of that (with the auto-complete) is to manually delete the entries. Basically, click in the box, hit the Down key, and then hit delete. Repeat 1000-2000 times. Also, if you're using the Google Toolbar you need to clear the search history in there as well(click on the button that says Google and click Clear Search History).