Hai ragione, un tavolo così grande non è utilizzabile. Se hai bisogno di un vero sistema di mantenimento dei messaggi, dai un'occhiata alle soluzioni NoSQL (come HBase, Cassandra, MongoDB ecc.) dovrai semplicemente dimenticare tutto ciò che sai sui database relazionali.
Con MySQL puoi comunque fare qualcosa di scalabile se dividi la tabella in pezzi molto piccoli. Fai in modo che una tabella conservi messaggi di massimo 1k utenti (dovrai scrivere tutti i messaggi due volte a meno che entrambi gli utenti non provengano dalla stessa tabella). Inoltre, mantieni non più di 1k tabelle in un DB, creane automaticamente un altro quando viene raggiunto questo limite. Avere diversi database (anche su un server fisico) renderà facile per DBA trasferirli su un nuovo server quando quello corrente si sovraccarica. Per ricevere i messaggi di un determinato utente il tuo codice dovrà ottenere il DB/tabella richiesta da una mappa che avrai.
