It's going to be hard to give a satisfying answer because it depends where the virus is hiding. Generally speaking, good malware authors are better at finding places to hide than virus-scanners are at routing them out.
I'm not malware expert, but for the purposes of this question, I'd break malware into the following categories:
- Hides somewhere on the filesystem, maybe by injecting itself into another application. Simply performing a full re-install of Windows should fix this.
- Infects masterboot record. In this case you'll need to fully re-format all attached storage devices, including the partition table and MBR.
- Jumps over the network. In this case it will come back as long as there is one infected machine on the network. Your best-bet is to re-install and apply all Windows Updates (to patch known vulnerabilities in network protocols) prior to connecting the machine to your network (which kinda sounds like a catch-22 unless you're good with firewalls).
- Infects firmware, like BIOS or programmable memory on things like network cards. I have no idea how common this is, but I can imagine it's possible, and it will re-infect when the fresh Windows auto-installs device drivers.
I think a complete partition-level format of the drive and re-install is considered sufficient, but if you're a tinfoil hattist to the point of worrying about hardware / firmware hacks, then you need new hardware.
[This is not my expertise, so I'm open to comments.]