¿Restringirlo respecto de qué criterio?
Lo más simple es hacer que el RAND corra sobre el resultado de una subconsulta a la que le apliques el criterio definido:
Código SQL:
Ver originalSELECT *
FROM (SELECT *
FROM registros
WHERE ( criterios)
LIMIT 0,5 ) T1
ORDER BY RAND() ;
(parece que Huesos52 y yo teníamos la misma interpretación)