Keep a log of deleted users and re-delete upon restore.
The GDPR contains exceptions for data storage for which it is infeasible or outside reasonable effort to delete individual records or you have legal compliances to uphold.
Isn't the log of deleted users subject to the GDPR then?
You can make a log of deleted users without it containing personally identifiable information, by just storing the IDs.
Anyway, think about the spirit of the law, and then think about how that interacts with backups. If someone asks to be deleted from your system, you do so, and then you restore a backup with their data, you have clearly violated the intent.