Re:
A lot of tension on this thread about nuking and paving. Holy crap!
You all need a vacation!
Does it really matter what the person does to make the customer happy? What matters is the final result.
Firstly, there's no way you can clean an infected machine 100%,because of the tricks involved to infect the computer.
THE SAFEST way, is to start fresh with the OS and apps.
I always make an image of the drive, so I have no data loss; in case the customer cries about something missing, i can always go back to the old hard drive and get it for him or her.
If it gets to a point where the performance of the operating system is affected, after the infection removal and a repair of the OS does not fix the problem, I recommend a reformat and because of the backup I have the loss of data is minimal to zero.
I never had a customer complain about a pave and nuke, especially since all of their data is back on the system.
Hardware and software can be replaced, but personal photos, files, can't.
As long as you have a solid backup, you should not worry about the OS and apps. You can always get the software, even if you purchase it and in most cases the customer has the CDs for the apps that ran on Windows 98 and now they are running Media Center.

I have a 50-50 situation about removal or pave and nuke,so I don't stress about either cases, but I do get a confidence boost when the customer smiles and genuinely thanks me for the service and affordable price.
Ultimately it's about the customer service, since some don't even care about the intricacies of the steps taken to remove the infection.
Your call if you want to stress about this process or not. It's not about laziness, incompetence or anything else in that range, it's about doing what works for the customer and for you.