Loss of hard drive capacity

Sounds like you are starting to get bad sectors on your HDD. I do not know under Mac but for PC did you try to run the chkdsk to see if it reports bad sectors? I am not sure if you have tried it but just in case:

1.Go into iTunes. In the lower right hand corner of the iTunes window, click on the "Display iPod options" button.

2. Down at the bottom of the new window, there should be a "Manually manage songs and playlists" option. Make a note which option is currently selected (we'll want to switch back to it if you want iTunes to manage the songs that are on your iPod). Select it. Click OK and close out of iTunes.

3. You should now be able to access your iPod as though it's a USB hard drive. Open My Computer. Make note of the iPod drive letter (ex: E: )

4. Click Start and go to Run. In the field, type in "cmd" (no quotation marks, obviously.)

5. At the prompt, type in "chkdsk e: /f" (no quotations, substitute your iPod's drive letter for the E: ) the "/f" switch automatically fixes problems found on the iPod. Depending on your computer's speed, the chkdsk utility should take a minute or two. The utility should display a list of errors on your iPod drive.

6. After the utility finishes and the prompt reappears, type "exit" hit enter and close the window by clicking the "x" in the top right hand corner.

May be time for a new drive. Good luck