Por favor que alguien me corrija, pero:
Código:
SELECT * FROM tabla ORDER BY Rand() LIMIT 10
debería andar.
Y si dices que es
casi siempre el mismo... entonces algo cambia.
Si prefieres aplicar shuffle() primero debes crear un array a partir de la consulta:
Código PHP:
while ($fila=mysql_fetch_array($resultado))
{
$array[] = $fila;
{
shuffle($array);
y despues un foreach para la salida HTML.
Suerte!