Your camera is not a picture archive device. The memory on the camera is designed for short term storage until you download your photographs on a hard drive and then back them up.
The memory card is like a disk drive, you may delete the file but the info is still there. The location of the information has been removed from the FAT table. (file allocation table)
Taking many photos and then placing some in the trash can creates problems with the FAT table over time. Since it is recommended that you download your photos and re-format the card, most of these issues do not build up a big enough problem to be noticed. If you never have reformated you storage device, then chances are you have so many errors on the card that it crashed, something that is common with storage devices once errors become part of the FAT table.
When you recovered the photos, the card reader had to restore the FAT table. Once it did, it wrote information that said the card could not hold any more information, don't add any files to the FAT table. After you recovered your photos on the computer, you need to reformat you memory card to clear out all errors in the FAT table and start from scratch. If you want to put your pictures back on the card from the computer, it is possible, but not a good practice.