bugman

Надо топать от того, как крутятся селекты по этой таблице. Исходя из предположения что чаще всего клиенту нужно показать все его сообщения, логично сделать хеш-партицирование по идентификатору получателя. Число партиций подобрать опытным путем. Если мускуль поддерживает двойное партицирование, второй уровень партиций можно нарезать по датам. Самые дальние партиции дропать или перекладывать в архив.

Разрешите взглянуть на задачу под другим углом — может не писать свои велосипеды очереди, а воспользоваться уже готовыми?

А в общем случае нужна некая структура для хранения текущего состояния, либо внутренняя (напр. банально сдвигаемый по исходной табличке маркер), либо внешняя (доп. табличка). У каждой свои плюсы и минусы. Но как только в игру вступят такие аспекты как — контроль доставки / обработки, перепосыл, мониторинг текущего состояния посмотрите снова на первый абзац.