t'ho modificato l'ultima parte,ti consiglio di scrivere il codice un pò più pulito magari spezzarlo in piu file e poi utilizzare un require alla pagina,di solito con la paginazione dei dati non ho problemi vedi se va....
Codice PHP:
<?php
include ("config.php");
?>

<style>

.titolo {
font:"Courier New", Courier, monospace;
font-size: <? echo $dimensfont;?>;
color: <? echo $colorT;?>;
}
.tabMess {

background-color: <? echo $sfondoTab;?>;
font-family:Arial, Helvetica, sans-serif;
color: <? echo $colorFont;?>;
font-size: <? echo $dimensionefont;?>;
}
</style>


<table width="100%" border="0">
  <tr>
    <td align="center" class="titolo"><? echo $titolo_guest;?></td>
  </tr>
</table>






<table width="40%" height="250" border="1" align="center" cellpadding="0" cellspacing="0">
  <tr>
    <td width="65%" class="tabMess" >

<?php
// parametri di configurazione
    
$filename="messaggi.txt";  // file delle frasi
    
$delim="<";             // delimitatore di frase

    // apri il file delle frasi
    
$fd=fopen($filename,"r");

    
//conta il totale delle righe, quindi dei messaggi
    //$totMex=count(file($filename));

    // legge il file
    
$contents fread ($fdfilesize ($filename));

    
//estrae per riga
    
$fraseexplode($delim,$contents);

    
//in ordine inverso i messaggi
    
$frase_reversearray_reverse($frase);


$mess_per_pag=2;
$tot_messaggi=count($frase);
$tot_pagine=ceil($tot_messaggi/$mess_per_pag);
$pagina_corrente ceil(($pagina/$mess_per_pag) + 1);

if(isset(
$_GET['pagina']))
{
$pagina=$_GET['pagina'];
}
else{
$pagina=1;
}




if (
sizeof($frase) <= "1")
{
echo 
"$PHP_SELF: Errore, nessun array, sto uscendo...";
exit;
}

for(
$i=0;$i<count($frase)-1;$i++)
{

$val[$i]=explode('#'$frase_reverse[$i]);


$nome[$i]=ucfirst ($val[$i][0]);
$citta[$i]=ucfirst ($val[$i][1]);
$messaggio[$i]=ucfirst ($val[$i][2]);
$data [$i]= ($val[$i][3]);

$table='<table width="100%" cellpadding="0" cellspacing="0" class="tabMess">
<tr>
<td  bgcolor="#999999">'
$nome[$i]. $citta[$i].  $data[$i].'</td>
</tr>
</table>

<table width="100%" height="40" cellpadding="0" cellspacing="0">
<tr>
<td bgcolor="#CCCCCC">'
$messaggio[$i].'</td>
</tr>
</table>

'
;

  echo 
$table;
}

// chiude il file
fclose ($fd);

?>

   </td>
          </tr>

<tr>
<td align="center" height="85">
   <table width="35%" height="85" border="0">
     <tr>
      <td width="35%">

      <form action="scrivi.php" method="post" name="form1">
       <table width="0" border="0" align="center">
        <tr>
          <td>*Nome:</td>
          <td width="82"><input name="Nome" type="text" size="10" style="font-size: 10px; font-family:Verdana"></td>
          <td>*Citt&agrave;:</td>
          <td><input name="Citta" type="text" id="Citta"  onFocus="controllaNo()" size="10" style="font-size: 10px; font-family:Verdana"></td>
                  <td>*Messaggio:</td>
          <td><textarea name="Mex" cols="20" id="Mex" style="font-size: 10px; font-family:Verdana" onFocus="controlla()"></textarea>          </td>
        </tr>
   <tr>
   <td>                        </td>
   <td colspan="2">*=campi obbligatori  </td>
   </tr>
      </table>
      <div align="center">
        <input type="submit" value="Firma" name="invia" onfocus="y" style="font-size: 10px; font-family:Verdana" />
      </div>
       </form></td>
      </tr>
         </table>

         </td>
     </tr>
</table>
<table width="200" border="0" align="center">
  <tr>
    <td>
    <?php
echo "pagina ";
$link="";
if((
$pagina!=1)&&($pagina<=$tot_pagine))
                 {
                  
$pag=$pagina-1;
              
$link.="[url='guest.php?pagina=$pag']Indietro[/url]";
                  }
                if((
$pagina>0)&&($pagina<$tot_pagine))
             {
                
$pag=$pagina+1;
              
$link.="[url='guest.php?pagina=$pag']Avanti[/url]";
             }
            echo 
$link;
            
?>
    </td>
  </tr>
</table>