Recovering deleted files is an all-too-common task that everyone runs into now and then.
Tl;dr, skip to last section.
The problem is that if your disk is low on free space, then files get fragmented which means that while plain-text files can still be relatively easily recovered (though it still requires quit a bit of work), binary files become all but impossible to recover. Granted, hard-drives are getting larger, which means less fragmentation, but only to a point. Drives are not written further and further out on the platter, then cycled back to the start, but rather, freed space from deleted files starts getting overwritten right away (“right away” meaning anything from the next boot, to the next write). Worse, the larger a hard-drive is, the longer it takes to scan it.
I recently accidentally deleted ~9,000 photos from a drive (stupid FOR command didn’t work as expected), and had to try to recover ~1GB of binary files. I tried over a dozen different recovery apps and got mixed results, and learned a few things. Different recovery apps have different functions and features. (Unfortunately I can’t currently list exactly which programs I tried and the results I got from them because they’re all on my other—SATA—drive which I cannot access because my motherboard died, and my current, backup system is only IDE.)
Some apps scan the file-system to find files that are marked as deleted and try to recover those. Some of these apps recover files regardless of if they have been overwritten, while others only recover those that are still “good” and ignore the others. The problem is that even if a file’s entire (and supposed) cluster chain is still marked as free (ie, has not been overwritten), how do you know if the file was previously contiguous?
Some apps use a different approach and scan all clusters on the disk to find file-types that they recognize (usually directories, photos, office files, and a few others), then recover whatever they can. The problem with these is that few file types indicate in the header exactly how large the file is, so how is the program supposed to know how many clusters to recover? Also, these apps can end up “recovering” files that were deleted long ago and have long since been overwritten, but the directory (marked as deleted) still exists in the directory.
Another thing to look out for is the way and detail with which the files are recovered. Some apps recover the filenames while others just give them sequential, numeric names. Some dump everything in a big folder, while others reconstruct the folder-system.
A quick look at the files shows the problems I mentioned. Some are completely corrupt and/or incorrect (they are not graphic files at all, but rather contain whatever happened to be at that cluster). Some are files that were deleted long ago and obviously contain nothing of interest. Some of the files are only partly good (eg half of the photo is visible, then corruption). Some files are absurd sizes (for example a small GIF file that should only be ~1-2KB is taking up >1GB because the app didn’t know how big the file should be). And so on.
Several of the programs that I tried have been mentioned in the other answers, but there’s at least two that have not been mentioned that I recall that I was impressed with.
I tried out Smart Undelete which I liked because it was capable of reconstructing as much information as possible (filenames, folder hierarchy, etc.) and even had a built-in photo-preview which made things easier. Unfortunately it’s a commercial app that costs $30 if you want to do more than just test. (Most trial software does a real scan and lets you see the results, but then prevents you from actually recovering many, if any files.)
Another one is Undelete360. It’s a program written by a single person and it’s free. While the skinned app smacks of cheaper, flashy, wanna-be software, I was impressed that it did about as good a job as the best of the commercial apps. Aside from some of the other programs that have been mentioned on this page, I would suggest trying this one. It even has a portable version which is good/ideal (why a recovery app would want to be installed as opposed to simply being run is beyond me; anyone novice enough to be unable to run an EXE and need a Start-menu shortcut is too green to do data-recovery and avoid messing things up further).
Make sure to sequester the volume/partition/drive/etc. that has the deleted files as much as possible (ie, don’t write anything to it anymore). Make sure to install and run the recovery software from another location, and don’t forget to set the recovery folder to somewhere other than the original volume. This way, you can safely run multiple recovery apps and see which one gives you the best results, and more importantly, get better results between them than using just one.
