[sfjailbird]

They already do this (the encryption-at-rest part). Deleting the data is still a hard requirement. Also, the keys are never seen outside of the centralized encryption service. Deletion is still a must.

[anyfoo]

Encrypt with an individual key for each user. Throwing away the key is indistinguishable from deletion.