Re: Not my field of expertise
Erase-on-restore is probably a nonstarter because it is technically trivial to *not* erase-on-restore, so the PII is still definitely available and identifiable. Likewise you've get to the root of the problem in that you need to be storing a unique (i.e. not anonymous) identifier to perform the erase-on-restore in the first place.
Anonymisation of your backups through something like tokenisation or classic data mastering techniques is really your only option. If you delete the tokenisation key or the master record, the record in the backup becomes (to some extent) anonymous. However even this is thorny because simply removing explicit PII is not necessarily enough to anonymise the data. Depending on the data context it may be trivial to reconstruct the identity, even if all of the unique keys and identifying fields are now random garbage.
Yes, this is hard. I suspect that, based on what the guidance eventually says, static/cold backups will have to be strictly time limited to a period less than what we're currently used to and justified as legitimate business purposes. As long as we're all perfectly clear with our data subjects that we're doing that, we should be fine.