RootKitRevealer hasn't picked up anything in ages for me.
I top off any malware disinfection routine with a full MLB, assuming that I found and disabled the original symptom and any other typical symptoms I look for. If a malware infection has managed to evade my usual tactics, as well as taking the machine home, disconnecting the disk and scanning it on my own machine with anti-virus and MLB and I've had zero or only partial success in removing it, I tend to recommend a reinstall to any customer at that point. My logic being, if it has exhausted most of my usual tactics and I've spent quite a while on it already, then how much longer do I need to spend to be confident that it is then malware-free, or whether I can actually be confident in my work at that point.
But the general rule is:
If malware had admin access any time during it's lifetime
If malware uses any sort of zero day vulnerability
The system might be toast.
I don't know about your experiences of dealing with malware*, but IMO a lot of customers refuse to admit that they realise they did something wrong**. Based on that, it's very difficult to answer either of those questions, and I think my customers would look elsewhere if I started handing out reinstalls like expensive parking tickets with the added annoyance of losing settings and "how things worked". I think my reinstall price is quite reasonable (£60), which includes bringing the computer back and setting it up on-site, and IMO it's a subsidised service. There's also the fact that I would have to spend some time attempting to remove the malware before going for the 'nuke it from orbit' strategy, either I have to give that attempted service away for free or it becomes an expensive malware removal job.
* - I'm not meaning to devalue your experience with this comment btw.
** - Yes, I realise that a lot of malware gets through purely via software vulnerabilities, and I've seen demonstrations where there isn't any outward sign that a malware infection just took place.