MySQL конечно.
Больше информации храниться будет, а также меньше нагрузки на сервер, т.к. запросы будешь осуществлять только на те сообщения которых нет, эдакий последний индекс сообщения (в виде индексации может быть дата создания записи в базе данных (почти эквивалентна дате сообщения по времени сервера) ).
Структура бд может быть проста, если есть поддержка пользователей, то хранить нужно и Primary Key пользователя.
Простейшая таблица:
id[int](primary key, auto incement) | user_id[int] | time[datetime] | message[varchar(255)]
Если сообщения ограниченной длины (255 значков), то использую varchar, если пространство на сервере не имеет значения, используй тип данного text, но советую ограничивать длину text field'а всё равно, дабы избежать перегрузки, когда кто-то захочет постануть 20 раз подряд, 200 страниц из какой-нибудь книжечки
Тип данных text также имеет динамичный размер, как и varchar, который зависит от длины содержимого (колличества значков).