c'è una pillola che si chiama qcs del genere gestire la paginazione in php...
Vai avanti con la lettura del thread perchè se mi ricordo bene ci sono diverse versioni...
In soldoni, dopo una prima query chiedi a php di contare i record restituiti dalla query ($num=mysql_num_rows($query))
Dividi poi quel numero per il numero di messaggi che vuoi avere per pagina (ad esempio 100 messaggi in tutto / 5 in ogni pagina )...