Creo que puede mantener su estructura de tabla actual para el contenido del mensaje. En lugar de agregar columnas separadas o banderas eliminadas, sería mejor tener una tabla separada para los buzones.
Entonces su tabla mbox actual:
id message sentby sentto created
Luego otra tabla para user_mailboxes
id user mailbox message_id
Tendría que hacer tres inserciones en total al escribir un mensaje, una en la tabla de mensajes, para cada usuario en la tabla user_mailboxes.
Así que sus datos de mbox se ven así:
id message sentby sentto created
1 Hi There UserA UserB 2015-01-26
2 Hello Back UserB UserA 2015-01-26
Y los datos de user_mailboxes se verían así:
id user mailbox message_id
1 UserA Out 1
2 UserB In 1
3 UserB Out 2
4 UserA In 2
Esto le permite eliminar filas individuales de la tabla user_mailboxes. Esto también permitiría futuros complementos al permitirle enviar mensajes a múltiples usuarios al mismo tiempo (una nueva fila para cada usuario), y le permitiría agregar más de un buzón si es necesario (Entrada, Salida, Papelera, Importante , etc.).
Para buscar el correo de un usuario para un buzón en particular, solo usaría una combinación
SELECT * FROM user_mailboxes LEFT JOIN mbox ON mbox.id = user_mailboxes.message_id WHERE user_mailboxes.user = "$user" AND user_mailboxes.mailbox = "Out";
Necesitaría una secuencia de comandos de limpieza a medida que elimina para asegurarse de que no haya mensajes huérfanos que no existan en la tabla user_mailboxes.