For web based services the rules change dramatically, because you are no longer in control of the data. Because the past has shown that companies seem to have a hard time to play nice with the data they store on behalf of their unsuspecting users there now is in some parts of the world a government entity tasked with precisely that: making sure that users right with respect to their data are respected.
If you don't like the way your filesystem deletes the data you can always cut up the platters.
A given text object will exist in the primary database, in its replicas or clusters, and in backups. If the outfit is at all legitimate, multiple backups representing frequent points in time, stored in multiple locations.
A binary object (say an image, video, or audio file) may exist in its originally uploaded format, several variants of different size, resolution, sampling rate, etc., and is often served through some sort of a content distribution network (CDN), which will have its own content management interface. Some of these are surprisingly primitive -- web-based forms in which a few score objects might be entered at a time, if you're lucky. Even script-driven purge methods are frequently limited as to the number of objects which can be included in a single request, and the number of outstanding requests which may be pending.
Given the large numbers of individual objects, scaling variations, redundancy, etc., deletion overhead can easily scale to tens to hundreds of millions of objects in a relatively short period of time (days to weeks). Dealing with all of this is fairly non-trivial. Especially if the site architecture didn't take these needs into consideration.
> Dealing with all of this is fairly non-trivial.
To Facebook's benefit, of course. I'm sure that Facebook would never think of using any user data flagged as 'deleted' in any sort of data mining...Facebook also has no incentive to spend the time to figure how to do deletions because the data is valuable to them. Why would they spent time and effort to make it possible to lose this valuable data?
(I'm talking about facebook here, not about the web in general)
If they're proper slaves / replications of one another, then yes.
If, as is commonly the case especially for marketing data, periodic cuts or dumps of the data are made at various points in time, and there's no mechanism for propagating deletions throughout the chain, then no, you're not assured of deletion. This isn't likely to be the case for a site's primary database, but could very well be the case for derived datasets. I can think of instances with, say, credit bureau reports in which erroneous data must be repeatedly deleted because it keeps getting re-injected into the system.
Facebook's September, 2010 outage in which cached data were being re-injected into the system exhibited a similar problem of cache coherence. http://www.facebook.com/note.php?note_id=431441338919
I'm sorry but this seems like a huge ignorance on the part of you on how DSes are designed. These issues are important.
Have you actually read the Paxos papers and the rest of the literature on this?