I would get a dos boot disk and first run FDISK and start with a clean system and new partition. Then format. During that process you will uncover any bad disk sectors and designate them as such. Then run the HP recovery CD. Then you know you have a clean system.

But then I do tend to overkill sometimes.