Boot any linux install CD in rescue mode.

dd if=/dev/zero of=/dev/sda
Wait lots of time until it give you end of device error.
dd if=/dev/urandom of=/dev/sda
Wait lots of time until it give you end of device error again. This will take lots of more time because it will basically exhaust the RNG capability of your computer.

After that you are ready to format the HD in any kind of partition table you want. Be warned that some Os installers like windows95 and windows98 ones will think that your HD has about several Zetabytes (about 1.000.000 TB or alot more). Just start again your linux install Cd and create a new big partition in this case. After that you can install windows if you want. Vista and XP installers rarely have such problems anyways.