Now I see what you were saying - thought the issue was they would not
delete at all. You are saying they will delete but return.
The only other place those should be is in the history index.dat file,
which unfortunately, is invisible using windows. I am under the impression
CCleaner will delete that file on reboot though.
C:\Users\ -your username- \AppData\Local\Microsoft\Windows\History\
In that history folder, there should a sub-folder called History.IE5 (that
you can't see) and in there, 2 files (that you can't see).
Desktop.ini
Index.dat
I never keep any history or autocomplete and there could even be
another invisible folder - not sure.
Here is what I did and you can try this if you'd like to. I have KillBox,
which is similar to Unlocker except it allows you to enter a full path
to the file to delete.
My history index.dat was 65KB before running KillBox and after
running it, 16KB. Which proves it did delete the old index.dat and
a new empty index.dat was created.
KillBox.Net:
http://killbox.net/
Here is how to use it. Use this path (copy it):
C:\Users\ -your username- \AppData\Local\Microsoft\Windows\History\History.IE5\index.dat
Close all programs.
Paste it into KillBox. Click the radio button to Delete on Reboot.
Single file button should be activated at that point. Then click on
the 'X' in the red circle - you should be promted to reboot. Then
go back and see if that got rid of the pests!
If that doesn't get rid of them, just not sure where they are hiding.