While going to school for my MCSE, I helped a fellow student setup his computer to run NT4. We had this same problem. His system had been used as a NT workstation with NTFS file system before he bought it.
The ONLY way that I have found to completly remove NTFS partitions is by low level formatting the HDD.
If the drive is a Western Digital or Maxtor IDE, you can download a program from their respective web site that will allow you to do this.
I have done this on many occasions, if I reinstall NT on the drive, the setup program reports it as a new drive. Then I setup the parititions and format them.
If I am going to use Win9.x, I use fdisk for Fat16 or ofdisk for Fat32.
Good Luck