I have had a couple of run-ins with viruses and malware before, and have found that a format and re-install of the OS is the easiest way of dealing with them.
But, my experience has simply been: PC acting funny > Run scan(s) to find virus/malware > Format & Reinstall > PC no longer running funny; scans don't find anything.
A lot of other guides suggest altering the registry, and deleting any specific .dll files and uninstalling any programs that relate to the virus. But that approach seems to be a more intricate/delicate approach than my "wipe it all and start over" tack.
So, will my approach actually remove a virus/malware? If you need specifics - Conficker and Trojans are the ones I have used this on.