My method is, everybody gets one warranty for malware removal, within 30 days of the initial service.
The warranty service means I don't do the malware removal again. I backup data, zero the drive, and reload Windows. Then if they get reinfected again, at least I know it wasn't my fault. At that point, they better be coming to me with their wallet out, because I don't feel bad about charging them again.
As for your really good clients.... well I believe in treating all clients with the same professionalism and fairness given to others, where possible. but I realize there are those times you want to give someone a break.... then go ahead and do it! (just don't advertise it haha).
But if you feel you shouldn't give them a break, then all I can say is in my experience the best way to justify anything to your clients, and satisfy your clients, is to SET THEIR EXPECTATIONS ahead of time. Let them know the nature of viruses/malware when they FIRST bring it to you, and tell them your policy up front including all contingency plans and warranty/guarantee possibilities. Then at the least, they understand they need to pay you again before they ever call you back, and you don't feel (as) bad for asking for their money again.
Then again on second thought, you could just tell them about Deep Freeze. *shrug*