If you boot with a Windows 98 boot floppy and run fdisk, you should be able to remove any partitions, including an NTFS partition with will appear as a "non-DOS" partition.
The Windows XP CD should then create a new partition, format it and install the operating system.
If booting with the floppy cannot recognise the hard drive, at the "A:\>" prompt type:
and press Enter to repair the master boot record. That might let you run fdisk.
What doesn't make sense is that, after formatting, "there is a lot of rubbish still on it that they want to get rid of". If it had been formatted properly, there should have been nothing on it.