If you use asymmetric encryption, you can keep the group of people who who can recover “deleted data” small. You could even have an independent party generate your encryption key pair, give you the encryption key, and your customer, on request, the decryption key (I think there is a business model for a non-profit here).
> generate a new encryption key every day for “data deleted today”,
The question is not can we encrypt at storage. We’re now talking about encrypting as a soft-deletion method, which means we need to know everywhere the data is stored at deletion time, whether to delete it or to encrypt it with this new “deletion” key.