M@Sik, Добавь поле `delete` записываешь туда id пользователя, удалившего письмо. Потом при выводе сообщений пишешь ... WHERE `delete` != '".$user_id."' ... Ну и добавить проверку при удалении сообщения, если поле `delete` уже заполнено(то есть отправитель либо получатель удалил у себя сообщение) то в таком случае удалять сообщение уже полностью.