когда-то реализовывала простой обмен личными сообщениями на одном сайте.
обошлась одной таблицей. Работает уже три года. Записей на данный момент около 100 тысяч
Может мой вариант кому и пригодится.
структура таблицы:
mail_id
mail_userid_from - id отправителя
mail_userid_to - id получателя
mail_text - текст сообщения
mail_data - дата отправки
mail_status - прочитано или нет получателем - чтобы выводить количество непрочитанных сообщений
mail_delete_userfrom - удалено/нет отправителем
mail_delete_userto - удалено/нет получателем
последние два поля как раз отвечают за "мягкое удаление". По умолчанию там нули. Если юзер удалил сообщение, то выставляется 1 и сообщение данному юзеру не показывается. Теоретически, если в обоих полях по 1, то можно грохать из таблицы такие записи.