Have found this online. You may want to have a try:
Go to Control Panel -> Control Panel Home (NOT the Classic View) -> System and Maintenance -> Indexing Options
As you can see Internet Explorer History is automatically indexed and can NOT be removed from Windows Search Indexing (i.e. storing ALL entries).
But, we can flush out the entries by clicking on Advanced and then Rebuild.
Once you click on Rebuild and re-open IE, aLL the previous pesky History entries in the address bar are GONER forever!!
--------------------------
From MS:
The index requires almost no maintenance. However, if the index can't find a file that you know exists in an indexed location, you might need to rebuild the index. Rebuilding the index can take several hours, and searches might be incomplete until the index is fully rebuilt.
1. Open Indexing Options by clicking the Start button , and then clicking Control Panel. In the search box, type indexing options, and then click Indexing Options.
2. Click Advanced. If you're prompted for an administrator password or confirmation, type the password or provide confirmation.
3. In the Advanced Options dialog box, click the Index Settings tab, and then click Rebuild. If you're prompted for an administrator password or confirmation, type the password or provide confirmation.