I'm not 100% sure what the EU laws and guidelines would be however; I suspect it's left to the member states to decide what to issue in regards to deletion of personal information. with that said I found a PDF from the UKs Information commissioner’s Office (ICO) and they state in this document that...
...the ICO will adopt a realistic approach in terms of recognising that deleting information from a system is not always a straightforward matter and that it is possible to put information ‘beyond use’, and for data protection compliance issues to be ‘suspended’ provided certain safeguards are in place
information has been deleted with no intention on the part of the data controller to use or access this again, but which may
still exist in the electronic ether. For example, it could be waiting to be over-written with other data.
information that should have been deleted but is in fact still held on a live system because, for technical reasons, it is not possible to delete this information without also deleting other information held in the same batch.
and in addtion to this in the next section it states.
The ICO will be satisfied that information has been ‘put beyond use’
if not actually deleted, provided that the data controller holding it:
- is not able, or will not attempt, to use the personal data to inform any decision in respect of any individual or in a manner that affects the individual in any way;
- does not give any other organisation access to the personal
data;
- surrounds the personal data with appropriate technical and
organisational security; and
- commits to permanent deletion of the information if, or when, this becomes possible.
So I suspect that they, themselves do not know the best approach so are leaving it vague. As long as you make the effort to show you deleted it and tried to make it un recoverable then I guess they are happy with that. As you and Graham Hill (comments) suggested, I would go with an industry standard such as BS EN:15713 or DIN 66399.
Accessed 15 May 2016
ICO Website for newest guidelines (UK)
ICO PDF on deletion