If companies stored customer data encrypted by keys that are held by the customer, they wouldn't have this problem. Furthermore, they wouldn't have to worry about deleting customer data either. The customer would have the power to simply deny access to the keys.
Tarsnap (a service that acts like your description) is quite nice, but the problem of "customer lost the keys" is a very real one. I love the idea, but someone really needs to come up with some decent key management (and offline backup and key migration) to make this consumer friendly.
What about Hashicorp's Vault?