I then got hit by a bigger problem, namely an auto dialler (games.exe, a known pest) which I acquired off a popup from another bulletin board. Grr. So I have done a bigger number of things, some of which seem to have fixed the original problem.
1. In Internet Explorer: Tools -> Internet Options: Clear History folder. Clear cookies. Clear temporary internet files (including offline content).
2. Right click Start: Properties -> Customize: Clear recent items. (There are different routes depending on whether you are using the pastel XP look or the classic Windows look but they're both there.)
3. Open Windows Explorer: Tools -> Folder Options: Show hidden files and folders. Un-Hide protected system files.
4. In Windows Explorer: Go to My Computer -> Local disk -> Documents and Settings: In every folder and subfolder, manually look for Cookies folders and Temporary Internet Files folders. Delete all cookies and temporary internet files manually out of them: IE 6 didn't automatically get rid of everything.
5. Go back to Tools -> Folder Options and reverse the two changes in 3. above.
(I did a couple more things which were more obviously to do with games.exe.)
Then restart the computer and see if everything works OK. It would be a good idea to check the length of time for recording History at this stage.
Thanks again to everyone for the help!