If its infected IE you need to format and start all over again...
On the contrary, I have frequently rescued a computer (and I do mean "a computer", singular) suffering from such problems without reinstalling Windoze. In fact, every time my then-housemate's seventeen-year-old nephew came to stay for a few days and "slept" in the spare room where the housemate's computer lived, I got to do it again. I became quite proficient at it in the end.
It was particularly interesting when he managed to infect it with something which detected when one was trying to visit the site that contained the only tool then capable of removing some of these nasties, and redirected the browser to a site that appeared to be the same but instead hosted an executable that would install even more nasties. Of course, I always look at the location bar, particularly when dealing with this kind of thing, and if necessary use an HTTP debugger to see what's really happening. Occasionally I'd have to go downstairs and download via my Mac, then drop the tool onto the PC over the network.
Still, I think the longest it ever took was about three hours, mainly spent in Regedit and then in Explorer deleting the things pointed to by certain registry keys, then rebooting, then repeating the process until I'd finally got them all... until the next day when a particularly well-hidden piece of crap tried to take over IE again, having apparently waited for a certain period of time after some other part of itself had been eradicated. Once I flushed that little bastard out, the machine was fine
Well, until the nephew came to visit again...
Still, it's pretty straightforward with the right tools and a modicum of dogged perseverance, and takes much less time than reinstalling Windows, then reinstalling all your applications, then recovering all your data from backups.