My Google search drop down (running in IE8) has a "clear history" link at the bottom, but the history only went back a couple of days which ties in with the last time I ran CCleaner.
If you haven't already got CCleaner, it's worth downloading (free) and running from time to time to clean up your PC.