It depends how deep the malware is embedded into windows. personally if the first try or two does not "cure" the problem I would recover via my stored backup image, or if I didn't have an image I would reinstall windows. Better safe than sorry.
Rule #1-always have an image of your Operating System(s) so in a disaster you can recover quickly and easily.
Rule #2-always have backups or an image of your data so you don't lose it in a disaster.
Rule #3- Refer back to Rule #1 and Rule #2.
I am not posting this to be a wise guy, but rather to help you in the future. I learned many years ago about rules #1 & #2 because I lost all my data when I didn't have a back up plan in place.
If you can't boot the windows CD/DVD/USB then I would try third party software such as gparted to format the disk and then reinstall windows. You can also boot off a linux Live CD such as ubuntu or Backtrack linux to recover the files you want to save prior to trying to format the disk with gparted and then reinstall windows.