Some things you could try (in no particular order):
1)
DBAN (Darik's Boot and Nuke)
While this might be a bit extreme, I've had to do it before so that I could reinstall XP on my desktop. It will guarantee that there's no remnants of any old installs laying around on the hard drive. Make sure to get the beta version as it's *MUCH* faster on SATA hard drives than the old version. (Old one takes 1 day for a 250GB hdd whereas the beta takes about 2-3 hours). For the 2.0 beta, you have to build it yourself. I can't remember offhand how to build it. I'm sure there's a readme included in the download though. (editv2)Look for the "DBAN for recent Intel and AMD computers" on the DBAN website. It includes an ISO for you to burn to CD-R/W (/editv2)
2)Your hard drive manufacturer's boot cd/hard disk tools.
The reasoning behind this is obvious since it'll check the disk for errors.
Since no brand was specified, here's a bunch of links.
Hitachi
Seagate (The DOS one should do the trick)
Maxtor (when you install it, you'll be able to install a bootable media builder).
Western Digital
(edit)
If you have a Maxtor/Seagate drive, the utilities *should* be interchangeable since Seagate bought up Maxtor anyways.
(/edit)
That's about all I got to suggest about that.