In the UK, for example, this is implemented by the Data Protection Act 1998: http://en.wikipedia.org/wiki/Data_Protection_Act_1998
The guidelines for complying with the DPA talk a bit about deletion here: http://www.ico.org.uk/for_organisations/data_protection/the_...
"If you offer users the option to delete personally identifiable information uploaded by them, the deletion must be real i.e. the content should not be recoverable in any way, for example, by accessing a URL from that site."
In fact the DPA takes it even further by requiring that personal data "shall not be kept for longer than is necessary" ie. you are supposed to delete any personally identifying data once you're done using it for it's original purpose (or another legal use). Granted, I imagine it would be pretty hard to bring a case against a company for either of these things, and I can't tell if the former is legally binding or just a "guideline," but it's not outside the realm of possibility...
I think you could easily argue that "needing it for an undo feature" is still a legal use for that data. But, thanks for pointing out that "delete" is a lot more legally loaded a term than I had assumed. It makes a pretty convincing case to call things "remove" instead of "delete".
It may not be "legally binding", but it certainly is a big risk: look at all the hoo-ha when (e.g.) Facebook/Adobe/etc. don't really delete your profile.
Note that I'm not saying they should/shouldn't: I'm arguing that there's many cases where indicating something is deleted (and not deleting it) can cause user outrage.
Oh, definitely; that's a great way to piss people off. But jd007 specifically mentioned that it might be "downright illegal", and that's what I was criticizing.
Where on Earth do you think labeling a button "Delete" is a legally binding specification with an incredibly specific required implementation?!