Ummm, you havent' already reformatted the card? You may just be getting bits of files left over from being deleted only. I recommend reformatting a card everytime you are done downloading images to the computer. That's the first thing I do when I put the card back in the camera.
Just to clarify... those bits of files are still there even if you format. Deleting removes an entry from the file allocation table. Formatting writes a new file allocation table. Low level format writes a new partition table and file allocation table. None of these options actually remove or change the data in the storage area of the card. That's why recovery software works. All the data is still on the card, even after formatting, it's just not indexed.
The errors showing up here though, look to me like corrupted data in the file allocation table. Running a recovery tool may actually get the images back.
The question however, is whether the card is damaged, and can't retain an intact table. Or whether the camera is corrupting the data on the card. Or maybe the data on the card just got corrupted once, and formatting will fix it...
(also, if you're paranoid and want to delete your data for real, there is "scrambling" software, which writes junk data to the entire card to make sure there are no old images.)