JavaDisperato, forse una soluzione c'e'; ho fatto qualche giro di prova e sembra funzionare. Prova pure te e dimmi se ti va bene.

Anzitutto toglierei dalla tua query (non da' fastidio intendiamoci) l'opzione DISTINCT in quanto sicuramente una SELECT sull'ID della tabella (che dovrebbe essere chiave univoca) ritorna una sola ricorrenza.

Poi ho gestito l'ID ritornato da Sql come un numero composto al massimo da 10 digit (10 e' il mio esempio ma puoi benissimo aumentarlo o diminuirlo in base alla conoscenza della chiave piu' grande che la tabella puo' contenere) utilizzando la Funzione Stringa Sql LPAD().
La funzione LPAD mi serve per avere una sequenza logica corretta di ID all'interno dello stesso Cognome+Nome.

La Select per cercare il successivo dovrebbe essere la seguente:

codice:
SELECT IdAnagrafica FROM anagrafica 
WHERE CONCAT(Cognome, Nome, LPAD(IdAnagrafica, 10, 0)) > CONCAT("".$_SESSION['cognome']."\", \"".$_SESSION['nome']."\", LPAD(\"".$_GET['id']."\", 10, 0)) 
ORDER BY CONCAT(Cognome, Nome, LPAD(IdAnagrafica, 10, 0)) ASC 
LIMIT 1
Mentre per cercare il precedente:

codice:
SELECT IdAnagrafica FROM anagrafica 
WHERE CONCAT(Cognome, Nome, LPAD(IdAnagrafica, 10, 0)) < CONCAT("".$_SESSION['cognome']."\", \"".$_SESSION['nome']."\", LPAD(\"".$_GET['id']."\", 10, 0)) 
ORDER BY CONCAT(Cognome, Nome, LPAD(IdAnagrafica, 10, 0)) DESC 
LIMIT 1
In pratica le due istruzioni si differenziano solamente per il ">" piuttosto che "<" e per "ASC" piuttosto che "DESC".

Controlla il posizionamento della funzione LPAD col valore $_GET['id'] perche' non l'ho provata in PHP ma in Sql e non sono certo che il gioco dei doppi apici sia corretto.