Leia a documentação do MySQL> neste ponto específico.
Em poucas palavras, o MySQL permite omitir algumas colunas do GROUP BY, para fins de desempenho, no entanto isso funciona apenas se todas as colunas omitidas tiverem o mesmo valor (dentro de um agrupamento), caso contrário, o valor retornado pela consulta é realmente indeterminado , como corretamente adivinhado por outros neste post. Para ter certeza, adicionar uma cláusula ORDER BY não reintroduziria nenhuma forma de comportamento determinístico.
Embora não seja o cerne do problema, este exemplo mostra como usar * em vez de uma enumeração explícita das colunas desejadas geralmente é uma má ideia.
Trecho da documentação do MySQL 5.0:
When using this feature, all rows in each group should have the same values for the columns that are omitted from the GROUP BY part. The server is free to return any value from the group, so the results are indeterminate unless all values are the same.
