It shouldn't be necessary to put a lot of work. Just delete the content, clobber it with blank fields, or randomized content. It really is very easy.
The problem is that your company's policy is to never truly delete content despite calling it "delete", there are many ways to weasel-word it ("many software subsystems don't truly delete" blah blah) but when someone asks a third party to delete something (s)he doesn't ask for it to have it marked deleted. Just delete it.
Surely not your fault though.
PS: there's no money in this world so that I'd work for a company with the morals and values of Facebook.
But for a large social site, it starts to become a more interesting distributed systems problem.
Even for a simple story with 4 likes, 12 comments, and likes on several of the comments, the data is sharded across several databases. Simple transactions no longer work. One option is looking for scalable distributed transactions. A more likely option is making sure deletions can be interrupted and restarted without losing state.
Now imagine a public figure whose post has tens of thousands of comments and hundreds of thousands likes. You may not be able to load all of those rows in a single request let alone delete them synchronously. Instead, you have to be able to process the deletion incrementally, reading and deleting some of the data then later picking up where you left off the last time you were interrupted.
Interestingly, the order of these operations can also be important. If you're interrupted between deleting a comment and deleting the likes on that comment, will you still be able to find the likes when you restart?
We've put a lot of work into a deletion framework that deals with these and many other issues. We're hoping to share more details about it in the future.
Each of the steps in building up the tree of comments, likes, etc. is a a couple writes at most. If that fails, you're left in a safe state. You tell the user it failed and carry on.
Deleting a post and the comments on it is harder. First, you have a potentially unbounded amount of DB rows to delete across an unknown number of shards. Second, you now have to worry about the order in which you delete things, else you risk being unable to retry in case one of these deletes fails. Third, unlike the inserts and updates, you can't just give up partway, as that's not a safe state to end in.
If you happen to have any more details about specific stories that reappeared, I’d love to try and figure out exactly what happened. Admittedly, that may be difficult now that several months have passed.
As one of the other commenters mentioned, your Activity Log is a better place to get a full list of your activity and delete it item-by-item. It also shows posts that Timeline omits and includes other types of content such as likes and comments. This help page may be useful https://www.facebook.com/help/activitylog and you can find your Activity Log at https://www.facebook.com/me/allactivity?privacy_source=activ...
I couldn’t tell from your description, but one possibility is that you only saw and deleted the stories rendered on your Timeline, which is just a summary of your activity.