Userei una tabella di ricerca per i messaggi che memorizzerebbero chi ha i diritti per visualizzare quel messaggio
table->message | table->messageUsers
id->0, message->'hi', user_id->1 user_id->1, message_id->0
user_id->2, message_id->0
In questo modo, se un utente elimina il proprio messaggio, in realtà sta solo eliminando la sua relazione con il messaggio, non il messaggio stesso. li rimuovi semplicemente dalla tabella messageUsers. oppure imposta un campo attivo su 1 o 0.