A breach of this law would cost a company 2-4% of their revenue as a fine. Seeing how these big companies operate there would be a lot of breaches.
I like GDPR, but a lot of people claim it to be too draconian. We'll see how it works out in EU.
Then, purging a person's data would come down to deleting that key from the system and from all backups of the keys.
That makes it a bit easier; the set of all keys will typically be a few orders of magnitude smaller than the data, and could be backed up using separate systems. Those systems wouldn't have to be updated often and access could be better controlled.
You would still need procedures checking nobody writes out non-encrypted data (including database keys), but that's doable; a first level scan would just run strings on your raw disks.
Disadvantage is that this would affect performance, especially for reporting services (a query gathering statistics over your customers would have to fetch all your customers' decryption keys)
A step up would be to hand out not bare decryption keys, but pairs (decryption key, expiration time stamp) encrypted with a private key that only your database knows the matching public key of. That allows your database to detect when your applications reuse decryption keys for too long. Depending on application architecture, that pair could even be a triple (decryption key, session key, expiration time stamp), and 'encryption' of course should use a salt.
I can't see that happening if they do any kind of offsite back up and archiving. They will purge you from the current master, say they purged you, and you'll be none-the-wiser.