При удалении сообщения одним пользователем, оно удаляется и у другого.

Добавить 2 поля в таблицу: удалил_автор и удалил_получатель.
И даже если оба "удалили" это сообщение, хранить его нужно 6 месяцев.
Потому что ФЗ 149 статья 10.3

Логично, с базы то скорей всего удаляется
Добавляете например таблицу, в которой будете хранить ИД пользователей которым не нужно показывать сообщение и ид сообщения
НУ и код дорабатываете

хз Запросы смотреть нужно

добавить таблицу связей, в котором будут id юзера id сообщения.

Можно в этой же таблице. Например, удалил автор - удаляем автора в таблице, но получатель остается и наоборот: удалил получатель - автор остался в таблице. Таким образом, можно написать условие при котором сообщения будут видны указанным в таблице юсерам: авторам или получателям, или обоим, или никому (если и тот и тот удалили сообщение).

Telegram - это работа всеми известного Павла Дурова, создателя социальной сети "Вконтакте". Начал им пользоваться сравнительно недавно. Отмечу несколько приятных моментов.
Во-первых, приложение невероятно быстрое, буквально "летает". Во-вторых, он удобен и прост в использовании. Можно сказать, ты отдыхаешь от навязчивых приложений, групп, реклам и т. д., которые есть в социальных сетях. Конечно, присутствует большая коллекция смайлов и стикеров, голосовые сообщения и многое другое. В-третьих, приватность - это еще одно достоинство telegram, его защиту еще никому не удалось взломать, хотя за это объявлено неплохое вознаграждение. Также удивили секретные чаты: таймер, который удаляет смс; при удалении сообщения в секретном чате одним пользователем оно удаляется и у другого. Это весьма удобно. Я пользуюсь telegram на android, но это возможно и на других платформах. В общем, мне весьма понравилось приложение, сожалею только о том, что в кругу моих друзей оно не пользуется популярностью, соответственно общаться не с кем.