When working on an e-commerce gig we would get "delete my data" requests from customers, which we're legally obliged to comply with. A script would delete everything we could from the DB immediately. Since we had 30 day backups, their data would only be deleted from the backups on day 31. I think this was acceptable to the GDPR consultant.
Going in to the backups to delete their data there in insane.
If I was legally obliged to delete data then I'd make sure I deleted, regardless of the purpose or location of the storage. If you can't handle a delete request you shouldn't collect the data in the first place.
But this obviously means building an extensive system to ensure the encoded identifier is the only thing used across your system (or a giant key management system).
In the past I’ve been a part of systems at exabyte scale that had to implement this. Hard but not impossible. I can see how orgs try to ‘legalese’ their way out of doing this though because the only forcing function is judicial.
If you don't want your data online then don't put it there.