O esquema deve funcionar bem, desde que não haja muitos destinatários da mesma mensagem. Não vejo como você poderia torná-lo muito menor ou mais eficiente.

O único problema de desempenho que vejo é que se você quiser fazer broadcast, ou seja, enviar a mesma mensagem para um grupo grande ou, digamos, todos os usuários do sistema. O envio de tal mensagem será muito lento (estive lá, fiz isso). Nesse caso, eu rastrearia o status dessas mensagens globais preguiçosamente, ou seja, criaria a linha de status para um usuário individual somente depois que ele tivesse aberto a mensagem. Mas se você não tem esse recurso planejado, eu diria que ignore esse problema por enquanto.