Se me ocurre una sola efectiva y es la de generar una cookie/session donde vayas concatenando los ids de los registros mostrados por pagina en un array, algo así:
Código:
$array[1] = '1,4,5';
$array[2] = '10,14,2';
$array[2] = '3,7,9';
...
Y en cada pagina tendrías que hacer un not in ($codigos) donde $codigos sería un join de todo éste array sacado a la posición de la pagina en la que estás (ej, si estas en la page 2 quedaría: 1,4,5,3,7,9.
Espero se haya entendido...saludos