but it could be a newly installed program correcting a registry entry (that is reset when you reboot)
Yeah... I've seen this happen a lot on Win95/98/ME machines. Especially if the newly installed program was a custom (IEAK) version of Internet Explorer. It seems to be the worst offender for causing this problem.
(I'm assuming you're running the 9x-family, WeirdAmi? I haven't seen this happen on NT/2k/XP.)
I'd probably check the machine for viruses, spyware and browser "helpers" first, though. If nothing shows up, download yourself a known-clean version of IE from Microsoft.
(Pretty much, any time you want to shuffle around the bugs on your Windows machine, just update IE. It's amazing how many bug fixes and new bugs are introduced each version!)