@nepster09 я бы вообще сделал немного сложнее.
Таблица messages поля int id, int sender_id, int recipient_id, text content
Таблица user_messages с полями int user_id, int message_id, boolean trash, boolean deleted
Если recipient_id = id_пользователя - письмо в папке входящие
Если sender_id = id_пользователя - письмо в папке отправленные
Если trash = 1 - письмо в папке удаленные
Если deleted = 1 - сообщение полностью удалено и не отображается ни в одной из папок пользователя
Соответственно при создании нового письма создаем 1 запись в таблице messages и 2 записи в user_messages
Можно входящие, отправленные и корзину вообще сделать отдельным полем int folder в таблице user_messages
@misc1 sphinxsearch.com, но в вашем случае его, наверное, будет много. Можно просто делать условие where like для нужных полей: WHERE cyrname LIKE '%" . $str . "%'