¿Es correcto escanear una tabla en MySQL usando SELECT * .. LiMIT start, count sin una cláusula ORDER BY?

No, esa no es una suposición segura. Sin un ORDER BY cláusula, no hay garantía de que su consulta arroje resultados únicos cada vez. Si esta tabla está correctamente indexada, agregue un ORDER BY (para el índice) no debería ser demasiado caro.

Editar:No ORDER BY Los resultados obtenidos a veces estar en el orden del índice agrupado, ¡pero yo no apostaría nada por eso!