AFAIK GDPR mandates that deleted data is no longer processed (used for marketing, analyzed, etc). I don't remember it saying anything about the data "existing"; nor could it given how backups work in our industry.
This is based on my personal layman's understanding. I am NOT a lawyer. I am NOT your lawyer. If you need legal advice consult a competent lawyer in your jurisdiction.
It is to prevent people going to their Bank, where they have a credit card or a consumer loan, or a mortgage, and say "can I please be forgotten/be wiped from your systems - oh and the loan too!".
You just store the keys separately, assuming one-way encryption (losing the key) counts as deletion.
But... if deleted data is no longer processed, does that mean it can not longer be used for targeting etc?
Your backups should be cycled after a few months and the deleted data will eventually not be present in any backups.