I have seen this behavior caused by McAfee and from the date and time being
incorrect. Checkpoints and Suggestions:
Check to be sure that your date and time is correct. Also, if you are using
McAfee, this will help:
McAfee gave this solution to the bug where VirusScan 6 stops your
Internet Explorer History file working.
Open VirusScan console
Select "Pick a task..."
Select "Change my VirusScan settings"
Select "Configure VShield background scanning"
Select "Customise your VShield settings"
Select the "Internet Filter" icon from the icons down the left hand side On
the "Detection" tab, in the 'Applet filters' section, remove the tick next
to "ActiveX Controls".
If this is not the case, run this edit:
Prevent IE History from Being Removed - Undo (Line 101)
http://www.kellys-korner-xp.com/xp_tweaks.htm
To use the Regedit: Save the REG File to your hard disk. Double click it
and answer yes to the import prompt. REG files can be viewed in Notepad by
right clicking on the file and selecting Edit.
Note: If you are using the Personalized Favorites Menu, Internet Explorer
automatically hides site that are rarely visited from the Favorites menu.