It's not a technical problem to solve, it's a legal one. If there is a crushing penalty if data that was supposed to be deleted shows up one day, companies will find a way to delete it.
One issue I foresee is that you can't legislate bugs away.
A bug is just a mistake, and the legal system already deals with mistakes in a variety of ways.
Umm you can. You can force companies to pass their code through an examination (even by a third party) and define a procedure of ensuring strict data hygiene. If they cannot pass each year, they will be subject to fines.