Do a drive wipe not just a format. A drive wipe is a destructive data removal. I have had to do this to several computers to make windows install correctly.
There are sevral levels of drive wipes. A quick wipe which makes one pass. A DoD wipe which makes 7 passes, and a Gutman Wipe which makes 38 passes. Unless you are Black Helicopter paranoid this is way over the top. One pass will do.
I like a product call Digital Dolly 1.0
. It has over a dozen hard drive utilities and runs from a RAM drive and does not need an OS.
For a simple drive wipe I recommend Kill Disk
. It is a freeware utility that can run from a floppy or CD.