I've had this same problem. I'm running a legit WinXP. No malware, spyware, virii, etc. At the advice of a professor I ran RegSeeker 1.55. I selected individual items instead of the Auto option. My QuickLaunch and Desktop toolbars constantly disappear each time I reboot. My desktop icons could be re-arranging each time, but I don't have them displayed (hence the use of the toolbar). I've also noticed that some quicklaunch shortcuts disappeared. Some of my programs reset as if they were new. And some keys I cannot access anymore. When I tried reinstalling some of the programs that were affected I got an Registry Error 5 (Cannot write to the registry). I'm still researching how to fix this. It seems that even the restore options in RegSeeker cannot restore certain keys, as they seem to be locked.

I'm going to try to restore them in safe mode.