Actually data backup is something 'standard' with more large corporations and their large customer bases. It's something there, but apparently those charged with destorying the documents forgot about them. Back-ups are usually done onto a computer medium and sent off site for storage (more often then not a 3rd party company). Those old salt mines are nice storage places.
While recovering data in this fashion is a pain, and everyone hates to do it (can take days to weeks), it can be done. Sounds like that's what happened here. The folks who tried to destroy the files were in one part of the company. But once that happened, the data or security folks knew about the backup policy and just started the procedure to recover.