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