Weird, You did click on the 'clear history' bit as well as 'delete temporary files'?
Close internet explorer and re-open.
Or if you wana get techy then right click on the START menu, select EXPLORE. Windows Explorer will open in the Documents & Settings directory for the username you are logged on as e.g. Administrator. Select LOCAL SETTINGS folder. Then select HISTORY folder and delete everything in history folder. If you break your PC dont blame me!
steve