There isn't a "record" of everything deleted. When you delete a file, Windows doesn't actually delete that data off the hard drive. What it does is make a note that the space that the file takes up is now considered empty. Eventually, Windows will write new files over that space on the hard drive. But if you use a file recovery program before Windows writes over that file, you can recover the file (because the file is still there, it's just "hidden" from Windows essentially).
Here's a metaphor that might help explain it better:
Say you have a restaurant (hard drive), and a customer (file) reserves a table (space on the hard drive). The customer sits down (file is stored) at their reserved table (space on the hard drive). A few minutes later you decide to cancel their reservation (delete the file). For example, their credit card was declined etc. You could go and remove them from the table (wipe the file off the hard drive), but the manager (Windows) decides it's easier to just let them stay until another customer (another file) comes who wants that table. The table is still occupied, but it is no longer considered "reserved", and if another customer wants that table they will get it right away (the first file will get overwritten by the new file).
Let's assume your file recovery software is a detective. The detective is looking for the first customer (a deleted file). The detective knows that the customer might be at the restaurant (on the hard drive) but not on the "reserved" list (marked as "empty" by Windows), so he checks every table. The detective can find the customer (if he is still there) even though the customer is not on the reservations list, because he is allowed to check every table (file recovery software can see files that are marked as empty). However, if a new customer came in and reserved the table (a new file has overwritten to first file), the first customer has already been asked to leave (overwritten) and is no longer in the restaurant (on the hard drive).
Phew, that was a much longer metaphor than expected, but hopefully it helps someone someday understand file recovery better
When you format a hard drive, you aren't actually wiping the whole drive. You are just "marking" the whole drive as empty (imagine removing everyone in the restaurant from the reservations list). Most of the actual data will still be on the drive (you don't make the customers leave), but again, it will be marked as "empty space" now (all tables can be reserved by new customers). When you install Windows, you are writing the Windows operating system files to the hard drive, so it will override any files in that area of the hard drive (new customers are replacing old customers). But the rest of the drive will be untouched. So in that scenario, there is a chance of recovering some files.
There is no guarantee, however, that at any point in that process you can recover any files. Basically, don't rely on the fact that a deleted file is recoverable. Always assume it's unrecoverable, and use a better backup system next time.
Hopefully that answers your question!
Edited by kokomodrums, 18 September 2014 - 03:50 PM.