> The more difficult part is deletion from backups, which is also a requirement.

How long do you keep your backups? If you just store them for, say, 30 days, that's fine. The EU regulators aren't going to come after you for a 30-day lag for all traces of data to be deleted, as long as that process is documented.

There's still one annoyance left: you do need to keep track of accounts/users who have deleted data, so if you have to restore from a backup, you can't restore any data belonging to users who have deleted their data within that window.

Otherwise, this is frankly not such a big deal. If you're storing backups for longer than 30 days, why? Where I work, if we had to restore from a 30-day-old backup, it'd be catastrophic for the business given how much data would be lost.