A couple of options...
Hopefully you catch this suggestion and give it a shot before performing a format and re-install/re-image. One of the newer, more agressive spyware/malware (sw/mw) removers that has had some recent positive reviews is
Malwarebytes' Anti-Malware. It identifies sw/mw differently than most other removal applications and has had very good success in removing some of the more difficult sw/mw that's out there. Download it and give it a whirl before taking the last resort.
On my IBM laptop, I am running Symantec AntiVirus with the latest virus definitions, which for the most part picks off almost every possible intrusion/vulnerability. For additional protection, I also run current versions of
Spybot-S&D and
Ad-Aware (free version) with the latest updates every few weeks to make sure nothing's slipped through. On my Mac G4 PPC tower, I'll run
ClamXav every now and then, but as Jamie hinted on, there's very few viruses out in "the wild" (I love when they use that term for this stuff

) that target the Mac, so it's rarely necessary, at least at this point.
I'd also suggest using a browser such as
Firefox or
Opera instead of IE (Internet Explorer). There's been countless exploits of IE, more so on previous versions that haven't been kept up to date with security patches. Firefox and Opera also have far more functionality available than IE, but that's a different discussion altogether.
Sorry to hear, dealing with viruses are never fun. Good luck and if you have any questions, let me know... -TD