Yes, take it out put it in the phat and format it. If that doesn't work, slap it in a sata capable laptop and do a full reformat.
Also I think that the firmware is stored on the console's flash itself and not the HDD so you should be fine(Correct me if I'm wrong guys). Back up your saves and such though.
If you can get your hands on a MAC and format it to HFS+ then back to FAT, that would help guarantee everything is completely gone. You would also be able to do a block check a lot faster for any errors.
Need an Original EBOOT???
Use your disc...