This is a big deal and it has many concerned over how it can be implemented as well as enforced.
Article 12 of directive 95/46/EC [1] specifies:
Member States shall guarantee every data subject the right to obtain from the controller:
...
(b) as appropriate the rectification, erasure or blocking of data the processing of which does not comply with the provisions of this Directive, in particular because of the incomplete or inaccurate nature of the data;
(c) notification to third parties to whom the data have been disclosed of any rectification, erasure or blocking carried out in compliance with (b), unless this proves impossible or involves a disproportionate effort.
Article 17 of the proposed regulation [2], a.k.a. the "the right to be forgotten/erasure" strengthens existing erasure/data minimization laws. You are already required to erase data upon request under certain circumstances, and under the circumstances described in article 17 (1) and existing law, you should no longer be storing the data to begin with.
[1] http://eur-lex.europa.eu/LexUriServ/LexUriServ.do?uri=CELEX:...
[2] http://ec.europa.eu/justice/data-protection/document/review2...
Backup this salt separately from the rest of the data in an easier to access media.
When deletion of a full row is needed, you just need to delete the salt from the comparatively smaller and quicker salt backups, as well as the live row+salt.
What they do have, that exceeds protection in the US, is the right for many EU citizens to request a copy of all of the information a company has on an individual, as well as, in many cases, the requirement that a company gain explicit permission before collecting or sharing personal information.
About this law: http://www.privireal.org/content/dp/poland.php