DELETE THE INDEX.DAT FILES:

Index.dat are files hidden on your computer that contain all of the Web sites that you have
ever visited. Every URL, and every Web page is listed there. (Also all of the email that has been
sent or received through Outlook or Outlook Express is also being logged.)
They cannot be deleted the usual way
When the Index.dat files are removed, they will automatically be recreated by Windows when your PC
starts up again, but they will be empty, 16k and 32k initialised files with all the history gone.

Here you can find a program to watch the contents of the index.dat.

First of all I've found a few free programs that might do the trick:
A)SSS (download) This program doesn't only clean the index.dat. It cleans almost your whole system.
(Look here for easy configuration)
B)Spider.exe (download) Very easy tool.
C)Index.dat Suite (download) Personally I only got errors trying to run it.
D)MoveOnBoot (download mirror mirror 2)
Tool to copy/move/delete files during the system startup. (Simple screen to BROWSE to the file you want deleted
and say bye bye on the next system boot.)

Then there's the option to manualy delete the index.dat files:

Users of Windows 95, 98:
On a Windows 9x computer the Index.dat files are located in the following locations:
C:\WINDOWS\Cookies\index.dat
C:\WINDOWS\History\index.dat
C:\WINDOWS\Temporary Internet Files\index.dat

Get rid of the index.dat by rebooting into MS-DOS and run the following commands at the command prompt:
cd windows
deltree/y cookies
deltree/y history
deltree/y tempor~1

Users of Windows NT, 2000 and XP:
On a Windows NT, 2000 and XP computer the Index.dat files are located in the following locations:
C:\Documents and Settings\[Username]\Cookies\
C:\Documents and Settings\[Username]\Local Settings\History\
C:\Documents and Settings\[Username]\Local Settings\Temporary Internet Files\Content.IE5\

Get rid of the index.dat by logging of your normal account and into an account with administrator privileges.
Create a new administrator account from Control Panel > Users if you have to do so.
Navigate to the folders locations using Windows Explorer and simply delete them. Since you are not logged
into those accounts, Windows is not using them and they can be deleted normally. (The next time you log on
the index.dat and folders will be recreated from a default template.

Users of Windows ME:
You are fucked. No, truly you are!
Use the instructions on this page