Tak tohle je buď vaše chyba, že závisíte na nespecifikovaném chování, a nebo chyba specifikace pythonu, že něco naspecifikuje a pak to změní. Já sázím, na první variantu. Bohužel programovat stylem "mě to tu běží" neznamená programovat správně. Nespecifikované (nebo nedefinované) chování je právě určené k tomu, aby mohl kompilátor nebo interpret zvolit rychlejší implementaci, pokud ji někdo vymyslí.
Já jsem zvyklý, že pořadí klíčů ve slovníku může být jiné dokonce při každé iteraci slovníkem. (To vyplývá i z jednoduché implementace slovníku například hashovou tabulkou. Jednoduchá implementace hashové tabulky řeší kolizní klíče spojovým seznamem. Odebrání a přidání klíče pak může tento klíč v tomto seznamu posunout na jiné místo). Dokonce i když vytvoříte dva slovníky stejným způsobem, může mít každý klíče v jiném pořadí. Do hashovací funkce lze totiž přimíchat například adresu slovníku v paměti, právě proto, aby byla menší pravděpodobnost, že dojde k hashovým kolizím právě na stejných klíčích.
Já se nechci hádat, určitě nedoporučuji spoléhat na "ledajaké" implementační detaily -- ale popravdě, většina jede na CPythonu, minimum na PyPy -- které navíc právě se trojkou nepočítá, a pokud píšu interní knihovny a můžu si určit, že jedeme na Pythonu 3.7 a více, tak nevidím problém. Ostatně třeba requests podporují až Python 3.3 (release 2012) a viděl jsem knihovny které mají 3.5+; kvůli čemu myslíte, že nepodporují starší desetinkové verze?