Unable to clean IE8 search suggestions

Here's one I can't figure out. This is a system running Windows Vista 64-bit and Internet Explorer 8.

I have Ccleaner set to clean all browsing history, search history, etc., and have even used the purging utility built into IE8 to do the same thing. But on a freshly-cleaned IE, I can begin to enter text into the search window, and if it's something I have searched for before, the search term pops up. This means that search objects are indeed still on the computer somewhere; how do you get rid of these?

I've attached a screen shot of this phenomenon. I had just run Ccleaner, also the cleaner built into IE8, and then opened up a new browser window. I typed 13 into the Search window, and at the top of the list, above where Google puts in its suggestions, is "13 oz rule," a Postal Service term I researched the other day.

post-47817-0-21007300-1305949658_thumb.jpg

In CCleaner, check the box for Autocomplete Form History: Cleaner > Windows > Internet Explorer > Autocomplete Form History.

Note: Close browser(s) before running CCleaner.

If you want to turn it off in IE, clear the box for Forms: Tools > Internet Options > Content > AutoComplete/Settings > Forms, then click OK.