You don't keep the backup forever. GDPR forces you to reasonable measures for deletion.

You could also keep a record of "to-delete" primary keys in event of a restore along with your backups.

All of this should have been implemented a long time ago, some European countries demanded this already.

I am surprised by the lack of imagination of people if they don't want to implement something (too burdensome, technically impossible,...) who can come up with decent solutions if it fits them.

A little anecdote for this: Recently I wanted to buy some insurance. The insurance company demanded wide leeway in handling personal data which by law (in Germany) has to be opt-in. I returned the paperwork, explicitly stating that I do not consent to use of the data beyond what is strictly necessary for the contract. I was told that contract can be made only with consent and that I could revoke consent later (the latter is mandated by law. What a bull-shit show. I am looking forward to GDPR coming into effect to give these businesses a middle-finger.

It's not impossible, it's just terribly complicates very simple things. No image back ups. No incremental image backups. No incremental backups of the DB. No backup od DB dumps. You need to reorganize everything, and in this case it complicates things a lot. For small and middle-size companies dealing with a lot of customer data (like hospitality industry), this is a major headache. And we do keep our records very well.