Ahh man, I feel your pain. As well as knowing what Mittens went thru. I also had a job of removing this nasty piece of malware, which had infected a friends PC after he clicked on a .txt file that was in fact an .exe (Curse of not having extensions on) from some dodgy crap he'd been downloading. I had a stab at this, tried vundofix and virtumondebegone both still left virtumonde replicating itself at every bootup.
After what was 2 days fiddling with different methods, I gave up, inserted my backup drive and restored his harddrive. Upon doing so, my boot up virus detector (motherboard feature) informed me that a virus was in the master boot record.
Now I never tried it, and it was just a theory of mine to delete and remake the master boot record before you boot back into windows after using vundofix/begone. I did mention this to Mittens, but I can't remember whether he actually tried it.
The little bugger is persistent and always hides somewhere, of course deleting your master boot record can cause problems, and you can try it at your own risk. You have my sympathys. But due to my experience with it, the only solution is to kill the disk. Just make sure in future, that you backup your initial installation so the reinstall process is less of a cumbersome chore.