se scrivi così:
codice:
<?php
for($i=0; $i < count($arrMatrUt); $i++){
        $MatrCall = $arrMatrUt[$i];
        set_time_limit(30);
        $count = mysql_query("SELECT COUNT(Id) FROM Utenti");
        $res_count = mysql_fetch_row($count);
        $tot_records = $res_count[0];
        $per_page = 20;
        $tot_pages = ceil($tot_records / $per_page);
        $current_page = (!$_GET['page']) ? 1 : (int)$_GET['page'];
        $primo = ($current_page - 1) * $per_page;
        $sql="SELECT  Id, Matricola, Nominativo, Sede, Telefono, Mail FROM Utenti WHERE Matricola = '".$MatrCall."' LIMIT $primo, $per_page";
        $query_limit = mysql_query($sql) or die(mysql_error());
        while($row = mysql_fetch_array($query_limit)){
                $cont = $cont +1;
                $id = $row["Id"];
                $Matr = $row["Matricola"];
                $Nom = $row["Nominativo"];
                $Tel = $row["Telefono"];
                $Mail = $row["Mail"];
                $Sede = $row["Sede"];
                $MatrOld=$Matr;
                ?>
                <tr height="20">
                
                <td><font face="Tahoma" size="1"><? echo $Matr; ?></font></td>
                <td><font face="Tahoma" size="1"><? echo $Nom ;?></font></td>
                <td><font face="Tahoma" size="1"><? echo $Tel ;?>
</font></td>
                <td><font face="Tahoma" size="1"><? echo $Mail ;?>
</font></td>
                <td><font face="Tahoma" size="1"><? echo $Sede; ?></font></td>
                </tr>
<?
        }
        if($current_page == 1) { // se siamo nella prima pagina
                $precedente = "<< precedente";
        } else { // altrimenti
                $previous_page = ($current_page - 1);
                $precedente = "<a href=\"?loid=1&mod=1&page=$previous_page\" title=\"Vai alla pagina precedente\"><< precedente</a>";
        }
        if($current_page == $tot_pages) { // se siamo nell'ultima pagina
                $successiva = "successiva >>";
        } else { // altrimenti
                $next_page = ($current_page + 1);
                //for($x=0; $x<count($OldId); $x++){echo $OldId[$x];}
                $successiva = "<a href=\"?OldId=";
                $successiva .= base64_encode(serialize($OldId));
                $successiva .= "&loid=1&mod=1&page={$next_page}\" title=\"Vai alla pagina successiva\">successiva >></a>";
                //$successiva = "<a href=\"?loid=1&mod=1&OldId=%OldId&page=$next_page\" title=\"Vai alla pagina successiva\">successiva >></a>";
        }
        $paginazione = "$precedente   $successiva";
        echo $paginazione;
        //include("pag.php");
}
?>
all'interno del for ottieni:
matr1 - 1
matr1 - 2
...
matr1 - 20
paginazione
matr2 - 1
matr2 - 2
...
matr2 - 20
paginazione

se lo metti fuori dal for ottieni:
matr1 - 1
matr1 - 2
...
matr1 - 20
matr2 - 1
matr2 - 2
...
matr2 - 20
paginazione