Why format - assuming you dont take regular image backups of your system (if you do, just restore your most recent image) - in 99.9% of cases, the computer can be cleaned of malware, quite esily in most cases. Sometimes it takes longer to clean than it does to format, but unless you have zero data on there you want to keep, then even this does not really make sense.
Some tools for you to help you today and in the future:
- Spybot Search & Destroy
- Hijackthis - a sensitive programme though, so if you are unsure about removing anything, post the results on wiki
And you should have a good internet security package that will help you avoid these type of things in the first place, and help you rid your machine of them when you do become a victim, dont bother with any of this "free" shite, you can't really put a price on internet security, so spend a few quid a year (last year F-Secure was available OEM for £7ish per year and Kaspersky can work out as cheap as £6 per PC per year) and get something decent. Here is some good-uns (that dont use 90% of your system resources either, like crap such as McAffee does):
- ESET Smart Security
- Kaspersky Internet Security
- F-Secure Internet Security