Je hebt gelijk, zo'n grote tafel is niet bruikbaar. Als je een echt berichtensysteem nodig hebt, kijk dan beter naar NoSQL-oplossingen (zoals HBase, Cassandra, MongoDB enz.), dan moet je alles vergeten wat je weet over relationele databases.
Met MySQL kun je echter nog steeds iets schaalbaars doen als je de tabel in hele kleine stukjes splitst. Zorg dat één tabel berichten van maximaal 1k gebruikers bewaart (u moet alle berichten twee keer schrijven, tenzij beide gebruikers uit dezelfde tabel komen). Bewaar niet meer dan 1k tabellen in één DB, maak automatisch een andere wanneer deze limiet is bereikt. Het hebben van meerdere databases (zelfs op één fysieke server) maakt het voor DBA gemakkelijk om elke database over te zetten naar een nieuwe server wanneer de huidige overbelast raakt. Om berichten van een bepaalde gebruiker te krijgen, moet je code de vereiste DB/tabel halen uit een kaart die je hebt.