Eu usaria uma tabela de pesquisa para as mensagens que armazenariam quem tem o direito de visualizar essa mensagem
table->message | table->messageUsers
id->0, message->'hi', user_id->1 user_id->1, message_id->0
user_id->2, message_id->0
Dessa forma, se um usuário excluir sua mensagem, ele está apenas excluindo seu relacionamento com a mensagem, não a mensagem em si. basta removê-los da tabela messageUsers. ou defina um campo ativo para 1 ou 0.
