Hola:
Si te ayudas de Ajax la idea es muy buena... yo lo hice en una página oara administrar una galería fotográfica y va bien. La idea es tener el array de los id's ordenados (siempre se puede usar el método reverse de los arrays), y un array asociativo de los elementos visitados.
El seguimiento de la paginación es bastante sencillo, según la página requerida se averigua que elementos ya fueron visitadas y simplementa se muestran, y las que no, se buscan con ajax (... bueno, la teoría puede parecer sencilla, pero hay que trabajarla)
Saludos
