You can also try a virus scan or trojan sweep. Lots of spyware hide what's really happening - a trojan attack. Ctrl-Alt-Delete and check the process list for anything you don't recognize. Google it, and I can nearly guarantee you'll find a trojan. Usually Symantec or some other company has a webpage with removal instructions. The whole procedure can be much quicker than a reformat.
The last trojan I pwn3d was detectable by Ad-Aware, Spybot, and HijackThis, but none could get rid of it all. Sometimes you just have to get down in the dirt and kill the weed with your bare hands
