Sounds like a Spybot.worm variant. Can I suggest
1) install a
free 15-day trial of McAfee VirusScan 9.0
2) disable System Restore
3) reboot into Safe Mode
4) run a McAfee antivirus scan of the whole system while in Safe Mode. It'll take a while if you have a lot of data, so maybe do this overnight.
Another recommended goodie:
Microsoft Baseline Security Analyzer.
If there are multiple people using this computer, ask them if they've noticed anything weird going on when they were using MSN Messenger, since one of the places where I've seen this mentioned is
Bropia worms that spread using MSN Messenger.