Our approach would be to add some filters into our 'restore' pipeline which drops the problematic data should we ever attempt a restore, but I don't think it's good enough, and we have to maintain a list of user id hashes or such to power the filters.
Edit: I mean, in a way that won't eat a lot of costs. I can imagine a malicious group opening and demanding deletions for 1000s of users which would mean a deletion job running on a large number of these 20TB backups, say 100 daily backups and for multiple users?
You may even be okay to just reply to the user that you've deleted all active copies of the data and it'll be fully gone when your backups expire in 30 days.
IANAL tho.
I am not aware of any provision within GDPR that allows anyone else but the individual person (and courts) to request deletion of their personal data. So I think your example is highly unlikely to ever happen.
We have automated systems to deal with requests in that category, it would probably have to be in the double-digit percentage of our customer base before we see any significant impact on our ability to conduct business.
We know which dat belongs to which customer, we know which data we must delete if requested, we know which data (eg invoice related for bookkeeping) we must keep even if requested to delete personal data.
If we ever piss off such a large portion of our customers, that they want to delete their accounts, GDPR-related requests will be the least of our concern.