I have had some experience with removing spyware form infected machines.
I use AVG antivirus the paid version, and Webroots Spy Sweeper.
When I have cleaned up infected PCs, that kills it all.
You can get a free version of AVG at
http://www.avg.com/
For spyware, there are two good free ones.
Adaware
http://lavasoft.com/
Spybot Search & Destroy
http://www.safer-networking.org/index2.html
The latter one has to be run a few times, but it is a good product.
Some say you have to boot to Safe Mode when running these apps.
I never have, and they have cleaned up an infected PC just fine.
In this same forum section are older threads on how to remove spyware/viruses too.
And that tool with Windows called Windows Restore I think it is called, I never run it.
Your backups it keeps can contain a viruses and spyware, and it gets put back on again.
I back up all of my files by an external USB hard drive, so when it is time to clean the PC when it is running bad, I format, reinstall the OS, and then restore my backed up software.