This worked for me....
Have you updated to WinXP SP2???
I use the newest freeware version of ad-wareSE v1.05 (make sure you run the update feature every time you use it).
I also use SpywareBlaster, also available as freeware at javacoolsoftware.com Make sure you update it regularly and after updating make sure you enable the new updates. This product doesn't scan your system, so much as it protects it from spyware installing in the first place.
I have also used HiJackThis for one particularly insidious infection about 6 months ago, but the new versions of ad-aware and spyblaster should work fine. Be very careful with HiJackThis. You can nuke some important registry entries. When I used it, I nuked all of the results and it didn't hurt my system but I probably just got lucky and wouldn't recommend it unless you know what you're doing.
I would also recommment scanning with NortonAV or some other AV program. As already mentioned, you have have to turn off system restore to get rid of some viruses and parasites. Don't forget to turn it back on when you're done!
Oh, and don't forget to disconnect your internet connection when scanning, rebooting, etc.
Good luck