One possibility to check:
I've had the same problem erasing History in IE for a long
time and none of the usual suggestions helped, including
deleting the folder in DOS, accessing Internet Options
through Control Panel, purging all spyware, and crippling
any protective programs that were running.
However, I discovered that I had a separate "Internet
Options" screen available within my AOL browser that did
indeed let me clear the History cache. Apparently the
software from AOL (and maybe other ISP software as well)
can keep a "handle" on the History folder preventing other
processes from deleting its contents. This appears to be
true regardless of which browser (IE or AOL's) originally
went to the sites in the cache.
The path for deleting the history cache and other web
matters in AOL (6.0 for example) is as follows:
Settings > Preferences > Internet Properties
From there, the screens should look somewhat familiar and
the procedure will be obvious.
Kevin