I had this problem after running CCleaner on Windows XP Professional service pack 2 the other week and discovered this thread via Google when looking for a solution, although nothing in the above worked (apart from a re-install of XP but that's far too drastic!).
So I tried an experiment and for me I have cured the problem by deleting the hidden desktop.ini file in the folder above the history store
To do this, close IE7, then you need to open a command prompt in Windows via Start | Run | type Cmd in the box.
Hopefully this will open a command prompt already in the
c:\documents and settings\[user name]\ folder
Change the command prompt's directory to the local settings folder by typing
cd local settings
then type
attrib -h -s desktop.ini
to remove the hidden and system settings of desktop.ini
then type
del desktop.ini
to delete it.
Reboot the computer, restart IE7, history functionalilty seems to be restored and the desktop.ini file appears to be recreated by Windows XP.
Hope that helps.
