У меня такое раньше бывало, тут уже обсуждали это. Я так понимаю, клиент зачем-то начинает выкачивать старые сообщения, а так как сообщения не сортируются по дате написания, то они расположены по дате получения.

Vit01 недавно добавил в андроид клиент опцию сортировки по дате, неплохо бы такое иметь и в цезии.