Máte pravdu, tak velký stůl je nepoužitelný. Pokud potřebujete skutečný systém pro ukládání zpráv, podívejte se raději na řešení NoSQL (jako HBase, Cassandra, MongoDB atd.), budete muset zapomenout na vše, co víte o relačních databázích.
S MySQL však stále můžete dělat něco škálovatelného, pokud tabulku rozdělíte na velmi malé části. Vytvořte jednu tabulku pro ukládání zpráv pro max. 1k uživatelů (pokud oba uživatelé nejsou ze stejné tabulky, budete muset všechny zprávy psát dvakrát). Navíc neponechávejte v jedné DB více než 1 000 tabulek a po dosažení tohoto limitu automaticky vytvořte další. Mít několik databází (dokonce i na jednom fyzickém serveru) usnadní DBA přenos každé na nový server, když se aktuální přetíží. Chcete-li získat zprávy určitého uživatele, váš kód bude muset získat požadovanou DB/tabulku z mapy, kterou budete mít.