> 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.

Most backup systems allow restoring only specific files. It could happen that some random document in an archive was accidentally erased or overwritten, and nobody noticed for a year until they need to reference last year's document. You wouldn't overwrite your whole archive by restoring a 365 days old snapshot to fix it.

> 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.

That seems like a big annoyance. The only way around it is a 2nd database that removes certain data in case a backup is ever restored. Ironically, keeping data on the data you need to delete.

Many regulated industries need to store data for multiple years, often in a secure format e.g. WORM storage

That's fine, you're allowed to store any data you are required to for some other regulatory or legal reason.

In the very worst case, let the customers know you had to recover with the backup and tell them to delete again. How often do you really need to recover from back-up anyway?