Seems an over complication
1. Inform user you have encrypted backups that may hold data on them
2. You can't delete the data in those backups as it's not technically feasible or practical, you can refuse a delete on these grounds.
3. You will remove them after X months/years or whenever the backups go into rotation.
4. If you do restore a backup after the period you removed the user, but before the user was removed in the data, just re-run the delete function again.
However to re-run the delete function again, you need to keep some personal data of who to delete, so in theory you can't delete them if you've forgotten them... Now I'm pretty good at forgetting things according to my wife, so I've deleted her and I now get excited to see a strange woman in my bed at night