@Danimal, that's a good question. I was actually thinking about having a flavor of Linux in the VM, and cleaning up messes in Linux is relatively easy, especially if you still have the support of the host OS. In general, an OS in a VM behaves just like a host OS, but the fact that it is held in a virtual environment means you always have access to the host OS and only have to worry about the VM being screwed up, not the whole computer. So, you still have access to the Internet, any shared folders on the host, a computer that still boots, functions, etc. In that way you can freely concentrate on just cleaning the malware or the problem in the VM.
With programs like VMWare and VirtualBox, you can create snapshots of states and then revert back to them very easily. It's like System Restore on steroids. Often if I have a certain state in a VM that is just working perfectly, I will export the VM as a virtual appliance and keep it stored as a backup. Then I can easily reload it back when I want, even side by side with the current state. Generally if one wants to play with dangerous stuff in a VM they use these tools so that reverting back happens in seconds, and there really is no need for a traditional cleanup.