Well depends , I dont like the traditional domains and we basically only use RDP, the clients are plain stupid and completely locked down under a GPO.
Basically we dont have this problem.
In case you need to remove something specific I suggest writing a powershell/bat script to do so, use it as logon script.
Generally block the outgoing port of the malware on the main firewall.
I agree with you that 'locking' the stations so that they are fresh on boot is a good idea, PXE comes to mind.
There are tools such as deepfreeze which basically locks a certain snapshot and restores it.
Damnit Im way too busy to continue this post, its been open for 3 hours now , Ill post some more when these bitches leave me alone