I'll tackle a few of your points:
Yes, it's true that if we simply erase the contents of a private message as our deletion method, the search is still functional, but the usefulness of it is hurt enough to make it a useless feature, IMO.
Useless for what purpose? I don't see how the search feature becomes less usefull here. I am still able to search through all of the messages that I wanted to keep. Obviously, I only want to search through old messages that I wanted to keep for that purpose. The fact that deleted messages are gone does not make my search of archived messages any less usefull.
So, assume we've offered the ability to erase the contents of private messages. Is that good enough?
Yes, although not optimal.
So, okay, rather than erasing the contents, the message itself is removed from the database. That mucks up the back-linking ability. And requires extra work on my part to appropriately deal with encountering a deleted message when back-linking. Do-able, of course, but extra work, which may accomplish nothing anyway.
This is such an easy fix. Just eliminate the ability to link personal messages. With only two people messaging back and forth, linking is really not that important of a feature. Or, create a screen that says "deleted" to replace the removed message, similar to how you deal with deleted public messages.
Should a person be allowed to delete only the messages they've written, only the messages that've been written to them, or both? If they can delete messages written to them, surely a scenario can be imagined in which the author of the message would object to their message being deleted.
Of course a person should only be allowed to delete the messages that they have written themselves. Messages from others need only be permanently removed from the recipient's inbox, folders, trash, etc. Nobody expects to be able to control content from others.
On a side and more technical note, physical deletion of a record uses a lot of horsepower on a large system, especially when there's a lot of it happening. It's one of those things that's insignificant by itself, but has a way of adding up to a huge load. And handling the possibility of the last record being a deleted one is a special challenge. If the system needs to access it (which it does when it's determining the number to be used for the next message), incorrect handling of a deleted record there would result in a fatal error condition.
I take this paragraph as you saying, essentially, that this is not an easy task and will take you some serious brain power to figure out the simplest and most efficient way of doing it. I realize this. I didn't think it would be easy. Based on what else you've done here, I know that you are talented enough to pull it off. I also know that eventually you will come up with an extremely elegant way of doing it, and will be able to take pride in your accomplishment.
But, all of the above said, let me throw this one out: Backups.
Well heck, one can't have everything. I would, however, suggest that you can limit this problem by implementing record retention policy with a schedule of dumping backup data every six months or so.
I appreciate your willingness to open this up for debate and consideration.
