So you have to do a clean install of windows and then reinstall OS X? What about Leopards duel boot program (can't remember the name)? Do you have to clean install windows then reload Leopard?
It's called BootCamp, and no, you don't as far as I understand. I don't use BootCamp, but what I know that it does is takes your Mac's drive, and partitions it such that there is a place to put Windows (or any other Intel based operating system) and helps you install it from a CD with drivers necessary for the Mac hardware. At least under Windows XP SP2. Once you've installed XP, you can boot either one or the other.
Parallels and VMware are a little different. They run as just another application under Mac OS X, with the virtual machine running as a (rather large) process as far as Mac OS is concerned, and the disk being merely a very large file as far as Mac OS is concerned. With Parallels or VMware, you can run your virtual machine while doing other things under Mac OS. So for example I have a Parallels virtual machine which I can run and do Windows things while at the same time run Safari, Mail, Photoshop Mac, etc all without restarting my computer.
There are some hardware things that aren't quite there, and the virtual machine runs a little more slowly, but if you're doing just the standard type stuff (email, web, chat, etc. though most of that can be done with the Mac itself) it's just fine. Back when I was employed I used the Parallels virtual machine to use the corporate apps that only ran under windows (lotus notes, outlook, etc.) when I didn't want to lug both my Macbook and employer issued Dell with me. Now I no longer have that problem, but eventually I'll be getting a different employer issued computer and will do similarly when that is the case.
Neither method requires reinstallation of Mac OS X (Leopard or Tiger.)