|It sounds like the Desktop Cleanup Wizard, which is enabled by default.|
To disable it, right-click your desktop and go to Properties to open Desktop Properties. On the Desktop tab, click Customize Desktop. At the bottom, uncheck "Run desktop cleanup wizard..."
The thing is that Desktop Cleanup Wizard should have created a folder on your desktop where it moved all the "unused" shortcut icons to. So, you should have been able to open it up, cut/paste the shortcuts back to your desktop, then deleted the now empty folder.
That function never accurately understood what was truly unused on my desktop, so it's one of the first things I disable when I install Windows XP.
Apologies if I don't respond to your reply immediately. I don't check this site daily, but you're welcome to PM me as a reminder.