You haven't mentioned the flavor of Windows you are attempting to install. Some versions of Windows install (above Windows 98, I believe) can recognise and remove Linux partitions and grub.
If you can boot into linux from a CD, I suggest zeroing out the drive. Any "Linux live" cd will do. For example, master drive on first ide:
dd if=/dev/zero of=/dev/hda bs=512
If you can boot from floppy (and have access to a Windows machine to make the floppy), the
Ranish Partition Manager might do the job for you.