Tienes razón, una mesa tan grande no se puede usar. Si necesita un sistema real de mantenimiento de mensajes, busque mejor las soluciones NoSQL (como HBase, Cassandra, MongoDB, etc.), simplemente tendrá que olvidar todo lo que sabe sobre las bases de datos relacionales.
Sin embargo, con MySQL aún puede hacer algo escalable si divide la tabla en partes muy pequeñas. Haga que una tabla mantenga mensajes de un máximo de 1k usuarios (deberá escribir todos los mensajes dos veces a menos que ambos usuarios sean de la misma tabla). Además, no mantenga más de 1k tablas en una base de datos, cree automáticamente otra cuando se alcance este límite. Tener varias bases de datos (incluso en un servidor físico) facilitará que el DBA transfiera cada una a un nuevo servidor cuando el actual se sobrecargue. Para obtener mensajes de un determinado usuario, su código deberá obtener la base de datos/tabla requerida de un mapa que tendrá.
