No entiendo tu consulta. ORDER BY necesita el nombre de un campo, no un numero por argumento. Como es que te funciona? En todo caso, fijate en el segundo comentario de aca:
http://www.forosdelweb.com/f18/sacar...-mysql-201300/
Si lo que dicen ahí es correcto, el RAND() va a elegir ordenar segun una columna aleatoria. Por lo tanto, tu paginacion debería tomar eso en cuenta y mantener el criterio en todas las paginas.