My opinion is that it is in fact guaranteed. It makes no sense for all other aspects of the dict behavior to be guaranteed and not this one.  This is what PyPy and CPython already do and there is no scenario where an implementation would be able to append a new pair at the end but unable to reverse the operation.

IMO, leaving this in an ambiguous state would created problems unnecessarily and it would preclude reasonable uses of the the ordering feature.