직접 해본적은 없지만, 경험상 RAND()의 시드값을 조정해서 풀 수 있을 것 같습니다.

사용자가 새로 로그인할 때마다, 같은 사용자라고 해도 다른 순서에 의해서 보여지기를 원한지만,

같은 세션이 유지되는 동안에는 순서가 고정되고, 페이지를 구현하기를 원하시는 것으로 보입니다. 맞나요?

사용자가 로그인할 때, 쿠키나 세션에 적당한 랜덤 값을 저장하시고, 이를 MySQL 쿼리의 시드로 사용하시면 문제가 해결될 것 같습니다.

이를테면,

SELECT * from T1 order by rand() 는 결과가 계속 바뀌지만,

SELECT * from T1 order by rand(100) 은 결과가 계속 같습니다.

이는 프로그래밍 언어에서 srand(...)에 같은 값을 넣을 경우 같은 순서대로 랜덤이 되는 것과 같은 원리로, 이를 통해 쿠키나 세션에 저장된 랜덤 값을 MySQL의 랜덤 시드에 넣으시면 1회 접속에서는 올바른 페이징 구현이 가능할 것으로 생각됩니다.