Требования:
- Работа с большим количество пользователей (>1000000) и сообщений (>10000000)
- Разделение сообщений на "входящие" и "исходящие"
- Возможность группировки сообщений в диалоги (диалог между двумя
пользователями)
- Возможность следить за тем, прочитано ли исходящее сообщение
- Удаление диалога и удаление отдельного сообщения (при этом у второго
пользователя ничего не удаляется)
- Высокая скорость работы

Интересуют мысли по структуре БД...

Я вообще всё в одной таблице сделал. Расставил индексы и нормально работает. С двумя таблицами манипуляций больше бы было (при удалении, добавлении + дубляж сообщений).

Okula пишет:
"Я вообще всё в одной таблице сделал. Расставил индексы и нормально работает. С двумя таблицами манипуляций больше бы было (при удалении, добавлении + дубляж сообщений)."

Дубляж нужен, иначе при удалении переписки одним человеком у собеседников тоже крякнется переписка с ним

Flyd, ничего не крякнется если правильно сделать.
Просто нужно добавить 2 поля (например, del_from и del_to). Значение этих полей по умолчанию равно 0 (нулю).
Если отправитель удалил сообщение изменяем параметр del_from на 1 (сообщение не удаляем), если и получатель удалил сообщение - проверяем стоит ли у отправителя в поле del_from значение 1 и только тогда отправляем.
Если стоит значени 0 то просто изменяем значение поля del_to на 1.
Отображение нужных сообщений не сложно настроить с помощью условий с полями del_from и del_to.

С выводом дмалогов ничего сложного нет.
У меня на сайте реализовано так:
Есть общая лента сообщений в которой пользователь видит все входящие и исходящие сообщения и может отвечать каждому из списка собеседников (притом сообщение увидит только тот кому оно предназначалось).
Есть ещё и отдельные чаты в которых общаются только отправитель и получатель. Эти чаты становяться доступны только тогда, когда получатель ответил на твоё сообщение.
А так же после этого действия в списках собеседников выводится ник того, с кем этот чат был создан.