AutoComplete doesn't want to erase on Internet Explorer 8

[RocShemp]

I apologize if this is the wrong forum for this but a search yielded no results.

As you probably know, IE8 usually autocompletes a web adress you're trying to type. Paranoid person that I am, I usually erase my browsing history regularly. Normally, this would erase the autocomplete entries as well. However, today I noticed that, although my browser history is indeed erased, the autocomplete remains unaffected. After searching on windows.com and other sites, I saw that you can errase autocomplete directly. I tried this several times but it stayed.

I even tried a third party program but ended up deleting it because it accomplished nothing.

This is weird because, until today, the autocomplete would delete by simply deleting my browser history. I saw online that I'm not the only one this has happened to but found no satisfactory solution.

I even tried unchecking the autocomplete boxes and deleting anew. But all that does is disable autocomplete altogether. SHould I check the boxes again, I see nothing was actually deleted. The only solution I found was clicking the red X on each autocomplete line (extremely tedious).

I've made no changes to my PC today. I even tried reseting IE8 to it's default setting and nothing. Any idea what the heck is going on?

My system is the following:

Intel Core i5 CPU 750 @ 2.67GHz 2.67GHz
4.00 GB RAM
Windows 7 Professional 64-bit Operating System
ATI Radeon HD 5670 GPU (512MB GDDR5)
msi P55M-GD41 motherboard