Как сделать удаления переписки?
Ответ как бы напрашивается - не удалять а прятать для конкретных юзеров.
Можно сделать таблицу, в которой будут находиться связь сообщение - пользователь. При удалении сообщения определенным пользователем, просто удалять нужную связь.