¿Por qué el orden del diccionario no es determinista en Python 3.3?

En las versiones de Python anteriores a la 3.3, el orden de las claves del diccionario era arbitrario, pero coherente. Sin embargo, en Python 3.3, este orden pasó a ser no determinista.

Este cambio es el resultado de una solución de seguridad implementada en 2012 y habilitada de forma predeterminada en Python 3.3. La aleatorización de hash, introducida para abordar vulnerabilidades de seguridad, hace que el orden de iteración de diccionarios y conjuntos sea impredecible y difiera entre las ejecuciones de Python.

Para deshabilitar la aleatorización de hash, puede establecer la variable de entorno PYTHONHASHSEED en 0.

Ejemplo contraintuitivo

Si bien el contraejemplo en la pregunta no produce consistentemente el mismo resultado en Python 3.3, su número limitado de ordenamientos diferentes se debe al manejo de colisiones hash.

Esta limitación ya no está presente en Python 3.6 y versiones posteriores, donde siempre se conserva el orden de inserción de los diccionarios.