You encrypt the data before it’s stored with a unique key, then destroy the key when the user requests it.

Doesn’t help for pre-GDPR data but that’s the way you should be building going forwards.

"We could have done it this way." doesn't pay the bills (or in this case, doesn't prevent steep fines).

Sure, it’s always painful to fix existing systems. In the future it should be no more expensive than business as usual though.

Will this satisfy GDPR requirements fully? What if that key had somehow been involved in an unknown leak in the past (of just the keys) and then the data is exposed somehow in the future?

Leaks are punished, as they probably should be, under gdpr anyways. But now do we have to account for all of the keys over time and have it be probably gone? What if we take backups of the systems that stores the keys? Do we have to purge those backups as part of the deletion request? What if they're terabytes in size?

Just thinking through edge cases here

> You encrypt the data before it’s stored with a unique key, then destroy the key when the user requests it.

That makes selects & joins on the data quite a bit more complex. Per-record & per-subject keys are … tricky.

Right, but you had assumptions built into your data store before, namely that you could keep all info about someone for eternity, and that you'd never have to correct it.