Formatting is a bit drastic, before doing that, why not try HiJack this, iadom suggests, or try running Webroot's online Spy Sweeper (this found some weird malware that both Ad Aware and Spybot S&D failed to find) - you can run it online at
http://www.webroot.com/wb/products/spysweeper/index.php (the 'try it for free' option at the top right of the page).
There are also some good forums on the web that help identify spyware and cleanse infected machines.
Personally, I'd go for that option first of all.