Have you been the one to use the hard drive since it was last formatted, or is it a drive purchased on Ebay for example?
That is a strange one from what you have said, if I had to speculate its possible the partition on the hard drive is corrupted in some way, however I really wouldn't like to say for sure.
I've only ever experienced this once and that was about 14 years ago now, as mentioned above. Using the NXE Dashboard has always been my preferred way to delete content, so its hard to speculate where something has gone wrong.