I've got several suggestions from colleagues of recovery software to try in linux and windows. I also found that this list of free data recovery programs at lifehacker was very useful.
This tutorial assumes that the memory card is formatted with the filesystem FAT16 (default filesystem in memory cards). The first thing you need to avoid is to write any data to the device where the deleted files were stored.
You should create an image of the device as soon as possible, in case anything goes wrong. In Linux that is pretty easy. Assuming that the memory card is mounted as /dev/sdb1, you need to issue the command
sudo dd if=/dev/sdb1 of=backupcard.img
I tried the following free software (ordered according to my taste): Recuva (win), recoverjpeg (linux/mac) and PhotoRec (win/linux/mac) (recoverjpeg and PhotoRec are available in Ubuntu via Synaptic). I also tried the commercial alternatives Stellar Phoenix Recovery (win) and Nucleus Kernel FAT (win). The latter two programs gave the same results as the three free programs listed above, so no need to pay for them.
The first program I tried was Recuva. It immediately recovered all the deleted files. Unfortunately most of the recovered pictures were corrupted or broken. By corrupted I mean that the pictures have one or more of the following "features":
- Pictures split in two or more parts
- In between a picture there is part of another photo
- Colors changed
recoverjpeg gave the same results as Recuva: restored all the photos, but only ~1/7 of the original files were successfully recovered with no problems.
PhotoRec only recovered the ~1/7 pictures that had no problems, ignoring the other corrupted files.
My conclusion: if you use windows try Recuva. If you are a Linux user, try recoverjpeg. And please check this list of Five best free data recovery tools.