Sugiro ter pelo menos o seguinte:

Usuários, Tópicos, Mensagens

• Todas as mensagens teriam um tópico
  • chave estrangeira:thread_id
• Todos os tópicos teriam pelo menos uma mensagem e pelo menos um destinatário (assim como o remetente)
  • chave estrangeira:to_user_id, from_user_id, message_id

A partir daí, você pode simplesmente atribuir alguns sinalizadores ao seu thread (to_user_deleted, from_user_deleted) que seriam atualizados de acordo.

É claro que há muito mais coisas a considerar, como os tipos de coisas que você deseja contabilizar. Por exemplo:

• Deseja exibir a mensagem atual em vez da mensagem inicial?
• Deseja permitir que os usuários marquem mensagens individuais como lidas ou apenas conversas?

Você precisa levar tudo isso em consideração ao projetar seu banco de dados.