Boot into "safe mode command prompt" using F8
Go to Root (C:\) by typing CD\
Now type C:\ del index.dat /s (<<spaces required) press enter
The Deleted Files will appear, then just exit for the finale now there really gone.
Do you think your History is really being deleted?