I think it's best to write zeros across a drive and start from a clean slate (so to speak), I've been doing it for a couple years now on my computers and customer computers. If I don't wipe the drive, the customer has a frown in less than two months complaining it is just as slow as it was before I fixed it. If I wipe the drive first, six months down the road the customer still has a smile and is thankful. If your drive is an IDE drive and the first drive, download a Live CD and issue this command in a root terminal:
dd if=/dev/zero of=/dev/hda conv=notrunc
And wait a long time till the prompt comes back, depending on your computer specs, this could be as long as 8 hours. The Helix CD as mentioned in Awesome's dd thread has a progress bar that helps with the patience, it won't go any faster but at least you can see it's still doing it's thing and you don't shut it down prematurely. With the Helix Live CD use this command:
dcfldd if=/dev/zero of=/dev/hda conv=notrunc
I've used both, works pretty slick. I also use bootitng
as my boot manager and use it's wipe feature more than any, it's like the dod version on the Helix CD and has a progress bar and is only a couple megabytes to download instead of 700MB for a live CD. The vendor also has CopyWipe at the bottom of the page which does the same and is free, so is bootitng till you install it to the hard drive for the boot manager features, then you're asked to pay $35.00 US after 30 day trial, but can be used to wipe, slide, create, resize partitions without obligation. It would be the best bet as you can use it to create the Windows partition the size you want for re-installing Windows, if you install Windows without a pre-made partition, it will swallow the whole drive, then you have to shrink it to install Linux.