smithfraud-c & zlob mediacodec trojans

[kyzerjose]

Thanks to the Ukranians. Anyway, thanks to some poor choices on my part, these pesky bastards have made there way onto my hard drive.
Updated versions of XSoftSE, Spybot S&D, Webroot Spyware & Norton 2006 and Regcure can't seem to permanently delete the culprits.
They replicate like bunnies. I continue to get a bunch of bogus "danger" pop ups and IE start up to websites even though I use Mozilla.
I've changed all of my online passwords from a safe (clean) computer.
I'm willing to buy a flash drive to save a few critical files etc.
Is a reformat the most effective course of action? I've got all the licensed disks etc.
Opinions wanted.

edit I've done all the scans and fix attempts in the "safe" mode too.