Paginación con resultados al azar

[chapi]

Hola a todos, alguien podrá tener la solución a este problema....??

Resulta que tengo una gran cantidad de registros en una base mysql que tengo que mostrar con php. Son miles de registros que se deben ordenar al azar... el problema es que los resultados tienen que estar paginados. Por lo tanto lo unico que se me ocurrió hasta el momento es agregar un campo a la tabla llamado IND al cual le doy un valor al azar por medio de RAND. Cada vez que tomo los datos aplico un "Order by IND desc" y por cron activo un script que actualice el valor de IND por un valor al azar de un registro al azar. ¿se entiende? Se les ocurre algo mejor??

gracias