They could encrypt each person's data with a unique key.
Then, purging a person's data would come down to deleting that key from the system and from all backups of the keys.
That makes it a bit easier; the set of all keys will typically be a few orders of magnitude smaller than the data, and could be backed up using separate systems. Those systems wouldn't have to be updated often and access could be better controlled.
You would still need procedures checking nobody writes out non-encrypted data (including database keys), but that's doable; a first level scan would just run strings on your raw disks.
Disadvantage is that this would affect performance, especially for reporting services (a query gathering statistics over your customers would have to fetch all your customers' decryption keys)
A step up would be to hand out not bare decryption keys, but pairs (decryption key, expiration time stamp) encrypted with a private key that only your database knows the matching public key of. That allows your database to detect when your applications reuse decryption keys for too long. Depending on application architecture, that pair could even be a triple (decryption key, session key, expiration time stamp), and 'encryption' of course should use a salt.
Then, purging a person's data would come down to deleting that key from the system and from all backups of the keys.
That makes it a bit easier; the set of all keys will typically be a few orders of magnitude smaller than the data, and could be backed up using separate systems. Those systems wouldn't have to be updated often and access could be better controlled.
You would still need procedures checking nobody writes out non-encrypted data (including database keys), but that's doable; a first level scan would just run strings on your raw disks.
Disadvantage is that this would affect performance, especially for reporting services (a query gathering statistics over your customers would have to fetch all your customers' decryption keys)
A step up would be to hand out not bare decryption keys, but pairs (decryption key, expiration time stamp) encrypted with a private key that only your database knows the matching public key of. That allows your database to detect when your applications reuse decryption keys for too long. Depending on application architecture, that pair could even be a triple (decryption key, session key, expiration time stamp), and 'encryption' of course should use a salt.