Use a Linux live CD like Knoppix and issue
Code:
dd if=/dev/zero of=/dev/hda bs=1M
That will zero out the drive. It will take 10 min maybe.
Then put in your windows CD and install Windows.
You can also try to boot your windows CD to the recovery prompt and issue
fixmbr for XP
fdisk/mbr for Win 98
Then install windows.
Windows is such a hog that it will overwrite everything. It doesn't know how to do simple things like write a MBR though.
I find better luck just zeroing the drive.