Deleting data is really really hard. If one is storing large amounts of data it is difficult to put a system in place which can prove that every copy in your posession has been deleted. Think about the work of sifting through thousands of write-once offline backups, be it tapes or CDs or whatever, locating the data, copying the original minus the data and destroying the originals. If that's not hard enough, what about data that's not in discrete files. Say there's a PostgreSQL database that's zipped and spans a thousand peices of physical media. The only way to delete a record is to load the whole database then redump it. And don't forget about regenerating all the index files. And dealing with obsolete file formats.
This sounds like a stupid problem, but in reality it is really tough to delete something and be certain that you've got it all.