Eccomi dopo i vari test che ho eseguito.
Ho provato il codice da te suggerito. Debbo dire che funziona discretamente, ma mi restituisce un lungo elenco di link, non migliaia come quello mio, ma solo centinaia.
Questo, debbo dire, non risolve il mio problema.
Poi c'è un fatto: ad un certo punto, arrivati ad un numero congruo di pagine, mi permette di procedere nella esplorazione dei record passo passo agendo "NEXT" posto alla fine della riga.
Cercando ancora ho trovato uno script che mi permette di ottenerequel che mi proponevo.
In realtà l'avevo già notato in precedenza, ma non lo avevo adottato perchè c'era da intervenire sui nomi delle variabili la qual cosa mi portava in confusione (alcune variabili che sfuggivano alla mia attenzione e che portava il codice in errore).
Tu mi hai fatto venire l'idea di mettere lo script in una funzione, dove i nomi delle variabili potevano restare come quelle originali.

Per questo te ne sono grato.

La funzione dove ho inserito lo script in questione ha come argomenti questi parametri:
$numpag: num totale di pagine
$pag: pagina corrente
$webpage: la pagina che ospita lo script
Per completezza posto la funzione che penso di adottare è questa:
Codice PHP:
<?php
function pagination_4($numpag,$pag,$webpage){
    $querystring = "";
    $n=20; 
    if (!$pag){
        $cur_page=1;
    }//apre di default la prima pagina se non è impostata la variabile $pag   
    if($numpag <= $n) {
        if ($pag>1) {
            echo("<a href=\"".$webpage."?cur_page=".($pag-1)."$querystring\"> < </a>\n");
        }        
        for ($pagina = 1; $pagina <= $numpag; $pagina++) {
            if ($pagina == $pag) {
                echo("<span class=\"selected\">$pagina </span>\n");
            } else {
                echo("<a href=\"".$webpage."?cur_page=$pagina$querystring\" title=\"Vai a pagina $pagina\"> $pagina </a>\n");
            }
        }
        if ($pag<$numpag) {            
            echo("<a href=\"".$webpage."?cur_page=".($pag+1)."$querystring\"> > </a>");
        }
    } elseif($pag <= ceil($n/2)) {//prime pag --> stampa primi n
        if ($pag>1) {
            echo("<a href=\"".$webpage."?cur_page=".($pag-1)."$querystring\"> < </a>");
        }             
        for ($pagina=1; $pagina<=$n; $pagina++) {
            if ($pagina == $pag) {
                echo("<span class=\"selected\"> $pagina </span>");
            } else {
                echo("<a href=\"".$webpage."?cur_page=$pagina$querystring\" title=\"Vai a pagina $pagina\"> $pagina </a>");
            }
        }
        echo("<a href=\"".$webpage."?cur_page=".($pag+1)."$querystring\"> > </a>");                  
        echo("<a href=\"".$webpage."?cur_page=$numpag$querystring\" title=\"Vai all'ultima pagina\"> >> </a>");                  
    } elseif($pag>$numpag-ceil($n/2)) {//ultime pag --> stampa ultimi n
        echo("<a href=\"".$webpage."?cur_page=1$querystring\" title=\"Vai alla prima pagina\"> << </a>");
        echo("<a href=\"".$webpage."?cur_page=".($pag-1)."$querystring\"> < </a>");              
        for ($pagina=$numpag-$n+1; $pagina<=$numpag; $pagina++) {
            if ($pagina == $pag) {
                echo("<span class=\"selected\"> $pagina </span>");
            } else {
                echo("<a href=\"".$webpage."?cur_page=$pagina$querystring\" title=\"Vai a pagina $pagina\"> $pagina </a>");
            }
        }
        if ($pag<$numpag) {            
            echo("<a href=\"".$webpage."?cur_page=".($pag+1)."$querystring\"> > </a>");
        }
    } else { //pagine centrali --> stampa n/2 prima ed n/2 dopo
        echo("<a href=\"".$webpage."?cur_page=1$querystring\" title=\"Vai alla prima pagina\"> << </a>");
        echo("<a href=\"".$webpage."?cur_page=".($pag-1)."$querystring\"> < </a>");                    
        for ($pagina=$pag-ceil($n/2-1); $pagina<=$pag+ceil($n/2-1); $pagina++) {
            if ($pagina == $pag) {
                echo("<span class=\"selected\"> $pagina </span>");
            } else {
                echo("<a href=\"".$webpage."?cur_page=$pagina$querystring\" title=\"Vai a pagina $pagina\"> $pagina </a>");
            }
        }
        echo("<a href=\"".$webpage."?cur_page=".($pag+1)."$querystring\"> > </a>");
        echo("<a href=\"".$webpage."?cur_page=$numpag$querystring\" title=\"Vai all'ultima pagina\"> >> </a> ");
    }
}
?>
Il link alla pagina è questo
Per completezza ho lasciato:
nella prima riga la tua funzione suggerita,
nella seconda riga la nuova funzione qui sopra descritta e che probabilmente adotterò,
e sotto la tabella è ancora presente la mia paginazione che naturalmente andrò a togliere perchè troppo invadente e dispersiva.