Do you have any antivirus software running? Make sure you update it and then do a scan. You may be suprised what you find. Also, try using more than (1) spyware remover. Spyware removers are not created equal. Some pick up spyware others may miss. Try using the following:
Adaware SE Personal (free)
Spyware Search and Destroy (free also)
That's NOT I repete NOT a windows error message.
It's a popup.
Go in to the services and stop then disable the messenger service. The messenger system is built in to xp. Spammers and other butt wipes use this to get around normal blockers and protection programs. Uncle Bill should be shot over this one.
Next disable the restore points. Disabling them will delete them.
Then from safe mode run your ad/spy/malware tools along with a virus scan. Do this off line of course.
Please come back and let us know how it came out.