DiskSalv4's CleanUp should remove all deleted files yes. I love it's salvage capabilities... once I repartisioned and formatted a drive just to still be able to recover most files from the different partisions on it.

For diskettes there are "BadFormat" but for harddrives I don't know... I seem to recall QuarterBack having something for this but I can't remember what or if it was just for backup purposes.
But IF a disk have errors it's time to can it... when an error first occure it seem to rappidly multiply over the disk. I once had just this problem and format would complain about one block... went into HDtoolbox and partisioned around this just to find more on previously working blocks... In a timespan of about 4hours I found more and more of this to I ended up with 15partisions on my 2Gb drive and gave up on it. :/