Paginação com Rand()

Pessoal, to aki num maior impasse pra resolver um caso de um cliente..É o seguinte.O cliente tem uma lista de produtos que são exibidos 20 produtos por página, com recursos de paginação e etc.. Até aí tudo bem..Faço a paginação numa boa usando LIMIT na instrução SQL.Esses produtos estão sendo exibidos ordenados alfabeticamente.Entao sempre ele vai exibir os produtos nas paginasPag1 - de 1 a 20Pag2 - de 21 a 40...e assim por diante..Agora se eu faço a ordenacao randomica no sql ( order by RAND() )Ocorre o seguinte..Não existe critérios para exibição.. Ou seja, ele simplismente vai escolher randomicamente 20 produtos na pagina 1, e randomicamente 20 produtos na pagina 2... e assim sucesivamente.Esta escolha sendo randomica, pode acontecer de produtos aparecerem em várias páginas.. e ao mesmo tempo produtos que não aparecam em nenhuma página!Eu não sei se você's entenderam bem o que está acontecendo ou se fui claro ao explicar.Eu até pensei em logo de inicio dar um select completo (com RAND() ) e armazenar tudo em array, e nas paginas seguinte.. 2, 3, 4... ao invés de puxar da base de dados, puxar os dados do array.. Porém acho que deve ter alguma solução mais viável pra isso.. Até pq qdo comecar a crescer o número de registros, vai ficar mto pesado o processamento.Quem puder me ajudar, ficarei grato.