pues deberías controlar el rango de valores que te coja en cáda página, y luego, los ordenas aleatorioamente,
algo como:
Código PHP:
...WHERE id>x and id<y order by rand()...
-EDIT-
[luego he visto] GatorV, podrías explicar la función de $seed en tu ejemplo?
un saludo!