Czy poprawne jest skanowanie tabeli w MySQL za pomocą SELECT * .. LiMIT start, liczenie bez klauzuli ORDER BY?

Nie, to nie jest bezpieczne założenie. Bez ORDER BY klauzuli, nie ma gwarancji, że Twoje zapytanie za każdym razem zwróci unikalne wyniki. Jeśli ta tabela jest poprawnie zindeksowana, dodanie ORDER BY (dla indeksu) nie powinno być zbyt drogie.

Edycja:inne niż ORDER BY Wyniki będą czasami być w kolejności indeksu klastrowego, ale nie zainwestowałbym w to żadnych pieniędzy!