Yes, but I hope nobody really relies on that ordering in their code, as, as you say, it is pretty inconsistent.

Eg. you can't rely on

  dict_b_keys = iter(dict_b)
  for key in dict_a:
      value_a = dict_a[key]
      value_b = dict_b[next(dict_b_keys)]
      print(f"{value_a} == {value_b}: ", value_a == value_b)

The problem with the proposal is that it will be even stronger: you either require '*' to sort in-place (I assumed that would be even worse and thus unacceptable, so I ignored that case — it seems others believe that to be a more realistic implementation), or require dicts to maintain a half-sorted map of integer keys.