Re: Not my field of expertise
Keep a log of those people who have successfull requested deletion.
If you restore a backup, re-run deletions from the time of the backup.
That log would be covered by legitimate interest.
Not sure your last point applies but I note only someone restoring data needs to be able to read the log and entries can be removed after the retention period for the data is reached.
Seems like a pragmatic solution to me.