I agree, that it is impossible to determine, with 100% certainty, that a machine is no longer compromised once it has been compromised. But, using the same logic, how can I be 100% sure that my OS did not come pre-packaged with a root kit, if the CD was produced outside the US or Europe? How can I be sure that my mechanic really fixed my car just because it drives better? How can I be sure my wife isn't cheating just because she says she loves me? Honestly, there are no absolutes in life.
On a mission critical server, or on any machine where absolute confidentiality was demanded, I might have to reformat, but for most everyday situations, its overkill. And now to answer your question specifically.
If a machine was, let's say, compromised by some variant of virtumonde, then I would look for BHO objects, DLL injection, search with an ADS scanner, yada, yada, yada. Eventually, once I had searched through the virtumonde dll's and located all its resources, I would finish up by performing probably 3 or four full scans, all with live CD's while the HD is not running. I would perform some packet captures and watch traffic carefully, scan with a port scanner or maybe just run netstat -a -b to determine if any processes have any strange ports open. Make sure no DNS poisoning of any kind has taken place. Look in run once entries, user32.dll injection, yada, yada. And after that, I'd call it a day.
Why? Because the likelihood that I'm still infected is pretty low. Most malware is going to show at least some sign of infection, even if its a spam bot that's trying to push as much spam every one second of every hour(trying not to be noticed), that is enough for me to get suspicious and start looking deeper.
But who can realistically take the time to reformat every time they get infected with every little piece of malware. On mission critical stuff, and on machines that demand absolute confidentiality, then yes, I would reformat. I would also take my backed up files and scan them with as many AV's as I could before putting them on the new machine. I might replace all my backed up files on a FAT32 file system first, just to make sure that no ADS's might still be lingering in some of those files, but I'm not going to do that every time some mid level manager downloads virtumonde from smilingpuppyscreensavers.com.