I've seen this problem of formats having absolutely no effect on a disk before. I never seen it on a hard disk before, only floppys. I don't have the slightest clue what causes it.

...Well, I guess that is less than helpful. I recommend you whack the hard drive with a modestly sized claw-hammer and invest in a new one. Whenever its happened on my floppy disks, I throw them out.

Maybe theres crap all over the write head or something, preventing it from formatting? Damn, I don't know. Wierd...