Во первых, прочитайте про нормализацию базы данных, если Вы делаете это на реляционной базе, то забудьте про создание отдельных таблиц для хранения одинаковых данных. Одинаковые данные должны храниться в одной таблице.
Проблему, про то что у Вас один собеседник удаляет сообщение, а другой оставляет себе решается тем, что записи необязательно удалять из БД, а достаточно проставить флаг, что пользователь удалил сообщение. А насчет партицированния таблицы или шардинга по серверам, оно Вам пригодиться на миллионах записей, поэтому не скоро.
Структура, при условии создания этого в реляционной структуре, у Вас должна быть примерно следующая, попытался описать быстро, поэтому извиняюсь, если что-то не учел в вашей архитектуре:
Таблица для хранения общей информации по диалогу.
- id INT
- name VARCHAR(50)
- created TIMESTAMP
Таблица для хранения сообщений диалога - здесь будут храниться все сообщения привязанные к диалогу.
- id INT
- dialog_id INT
- text TEXT
- created TIMESTAMP
Таблица участников диалога
- dialog_id INT
- user_id INT
- joined TIMESTAMP (указывает, когда участник присоединился к диалогу, чтобы не показывать сообщения, которые были до того, как он присоединился, возможно заменить данное поле на смещение по Id, чтобы это работало быстрее)
Таблица скрытых (удаленных) сообщений
- message_id INT
- user_id INT