Beh..... come impostare un menù di navigazione tra le pagine che sia "sensibile" alla pagina visitata te l'ho spiegato ben bene nel codice che ti avevo scritto in precedenza.
Con un pizzico di astrazione ci dovresti arrivare anche da solo.
Ad ogni modo, puoi risolvere semplicemente aggiungendo un conteggio dei record che escono fuori dalla query di select.

Codice PHP:
$result mysql_query($query$db);
$num mysql_num_rows($result); 
Una volta che sai quanti record sono stati estrapolati dalla query, e saranno quindi visualizzati dallo script, non hai altro da fare che dividere per il numero di record per ogni pagina e sai subito di quante pagine sarà composto il tuo catalogo.

Codice PHP:
$quante_pagine ceil($num $step
In fondo allo script devi modificare come segue:

Codice PHP:
if ($pag $quante_pagine) { 
$navigazione .= 
<a href=\"?pag=
$prima\">Indietro</a> 
"


################################

Il tuo secondo problema è semplice.
Se tu sei sulla prima pagina dello script, visto la seguente porzione di codice:

Codice PHP:
if (!isset($pag) OR $pag <= 1) {// eccetera 
Se $PAG non è dichiarato o se $PAG è minore o uguale a 1, allora $pag sarà sempre uguale a 1.
Per cui appena te apri la pagina $pag non è dichiarato e sarà sempre associato a 1.
Se nel menù di navigazione metti il link alla pagina xxx.php?pag=1, questa richiamerà sé stessa.
Credo sia ovvio.

Ometti questo link e vedrai che non avria problemi.