Você está certo, uma mesa tão grande não é utilizável. Se você precisa de um sistema de manutenção de mensagens real, veja melhor as soluções NoSQL (como HBase, Cassandra, MongoDB etc), apenas você terá que esquecer tudo o que sabe sobre bancos de dados relacionais.

Com o MySQL você ainda pode fazer algo escalável se dividir a tabela em pedaços muito pequenos. Faça uma tabela manter mensagens de no máximo 1k usuários (você precisará escrever todas as mensagens duas vezes, a menos que ambos os usuários sejam da mesma tabela). Além disso, mantenha não mais que 1k tabelas em um banco de dados, crie automaticamente outra quando esse limite for atingido. Ter vários bancos de dados (mesmo em um servidor físico) facilitará para o DBA transferir cada um para um novo servidor quando o atual ficar sobrecarregado. Para obter mensagens de um determinado usuário, seu código terá que obter o banco de dados/tabela necessário de um mapa que você tenha.