Masz rację, taki duży stół nie nadaje się do użytku. Jeśli potrzebujesz prawdziwego systemu przechowywania wiadomości, lepiej przyjrzyj się rozwiązaniom NoSQL (takim jak HBase, Cassandra, MongoDB itp.), po prostu będziesz musiał zapomnieć o wszystkim, co wiesz o relacyjnych bazach danych.
Z MySQL możesz jednak zrobić coś skalowalnego, jeśli podzielisz tabelę na bardzo małe części. Stwórz jedną tabelę przechowującą wiadomości maksymalnie 1k użytkowników (będziesz musiał napisać wszystkie wiadomości dwukrotnie, chyba że obaj użytkownicy są z tej samej tabeli). Dodatkowo przechowuj nie więcej niż 1k tabel w jednej bazie danych, automatycznie twórz kolejną po osiągnięciu tego limitu. Posiadanie kilku baz danych (nawet na jednym serwerze fizycznym) ułatwi DBA przeniesienie każdej z nich na nowy serwer, gdy bieżący zostanie przeciążony. Aby otrzymać wiadomości od określonego użytkownika, twój kod będzie musiał uzyskać wymaganą bazę danych/tablicę z mapy, którą będziesz mieć.
