Correct way to handle deleted messages and posts

The right way to delete message is to just mark it as deleted in the database.
Sure, we can also delete a record from MESSAGE_BODY if we keep a separate table just for message bodies.

Don't just mark it as deleted, but actually use a timestamp value for the 'deleted_ts' column.

The reason for that is that we will them be able to spot that the message has been deleted and not just 'does not exist'.

One advantage of knowing that it has actually been deleted and not just 'not found' is that we will be able to return a 410 response code instead of the normal 404

The difference between 410 and 404 is that search engines will not attempt to retry getting the same page again and again. The 410 basically says 'gone permanently' instead of just 'not found'

It may actually cause Google to delete this page from Google cache very fast.
Actually we can even give Google another hint to remove such page from cache. When we catch the 410 exception we may add an extra meta tag NOCACHE or NOARCHIVE, whatever it is that Google understands as 'don't use cached version'

This can be very helpful. And of cause by marking message as deleted instead of actually deleting it, we are not breaking the 'next', 'previous' navigation.

The 'next'/'previous' nav is another story, and maybe we actually should not use the 'next'/'prev' links of deleted pages because if many messages have been deleted we don't want to point to 'prev' which has also been deleted, we want to point to the first non-deleted page, but that will require a different logic. Later...

Also when we know that timestamp of when the message has been deleted we can show it to the user on the 410 page. So, we not only sending 410 response code but we can also show 'message was deleted on Dec 12, 2009' for example

This is also extremely helpful to the user.