IMO, the best solution is per-row encryption with the keys stored in a second database. This second database can still be backed up, with backups that have a maximum lifespan, eg: 30 days. When a user deletes their account, their decryption key is deleted, and is unrecoverable after the backup max life.
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.
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.