Tim_axe had some really good ideas. Here are a few more you might think of trying before refomatting/recovering:

1) Download HijackThis from http://www.webattack.com/get/hijackthis.html ]Snapfiles/WebAttack[/URL] and post it here or here to be reviewed.

2) In addittion to checking startups for anything unusual, shut down uneccessary startups. Check what you have on your list vs the list found here.

3) Again, in addition to turning off anything odd running under services, turn off all the extraneous junk that Windows has turned on. Look here for more information on what you absolutely need running and what you don't.

Good luck!