эйфория от новых возможностей прошла и вскрылись недостатки, на мой взгляд основные их них:
— Слабая производительность на 1-серверной БД. Особенно заметно на map-reduce по данным, которые полностью влезли в память.
— Особенности документо-ориентированной структуры. Многие переходили с табличных БД и тут понеслась: сначала радость, что не надо возиться со структурой, а потом расплата — в одной коллекции куча разных объектов и приложение регулярно читает из вроде бы известной коллекции что-то для себя неожиданное (очень старые объекты, некорректно измененные и т.п.).
— Целостность данных. Кто-то привык, что БД контролирует этот вопрос, вешают констрейнты и ловят ошибки в логе в случае какой промашки по части бизнес-логики. Монга же ничего такого сама не контролирует, ну и получаются внутри БД ссылки на объекты, которых нет.
— Отсутствие полноценных транзакций. Те, кто бросились все хранить в монге с ужасом поняли, что для биллинга нужно что-то другое. (должен оговориться, что не все пока поняли)

По моему мнению отказаться от классической реляционной БД в пользу монги может позволить далеко не каждый проект. Если перетаскивать какой-нибудь небольшой интернет-магазин, то с бОльшей вероятностью это принесет боль и страдание нежели ожидаемый профит. Эффективным решением будет параллельное использование монги и реляционной БД, но чтобы это имело смысл — проект должен быть соответствующих размеров. Для небольшого проекта городить такой огород контрпродуктивно.

PS Мое мнение основано на годичном опыте неплотной работы с монгой, опыт работы с реляционными БД — примерно 10 лет.

я вижу два варианта решения: простое и правильное.
Простое — это создавать по сообщению на отправителя и получателя. Тогда они становятся изначально независимыми.
Правильное — это то к чему вы почти пришли: сделать таблицу папок, таблицу сообщений и таблицу-связку: сообщение-папка-юзер.
таблица folder: id|name
таблица message: id|date|title|text и тп
связка: id|userId|folder|state|messageId + я бы добавил уникальный индекс по userId|messageId чтобы обеспечить целостность
state — состояние сообщения для пользователя: новое, прочитанное, в треше, удаленное на совсем
единственный нюанс тут — выборка для папки треш должен делаться по статусу а не по таблице папок

если у юзера могут быть свои папки, то структура должна быть немного иной: таблица папок будет ссылаться на юзера, а в связке userId нужно исключить.