Прав си, такава голяма маса не може да се използва. Ако имате нужда от реална система за поддържане на съобщения, погледнете по-добре решенията на NoSQL (като HBase, Cassandra, MongoDB и т.н.), просто ще трябва да забравите всичко, което знаете за релационните бази данни.
С MySQL все пак можете да направите нещо мащабируемо, ако разделите таблицата на много малки парчета. Направете една таблица да съхранява съобщения от максимум 1k потребители (ще трябва да напишете всички съобщения два пъти, освен ако и двамата потребители не са от една и съща таблица). Освен това съхранявайте не повече от 1k таблици в една DB, автоматично създавайте друга, когато този лимит бъде достигнат. Наличието на няколко бази данни (дори на един физически сървър) ще улесни DBA да прехвърли всяка към нов сървър, когато текущият се претовари. За да получите съобщения от определен потребител, вашият код ще трябва да получи необходимата DB/таблица от карта, която ще имате.