According to each (and also to the more accurate documentation you can get with perldoc -f each) your notion of "should" is incorrect.

Generally things should not work contrary to the documentation. For more on why there is no apparent order, see Re (tilly) 4: Flip Flop III - Musical Buckets.

In your case if you want to get the key/value pairs out in a particular order, it is probably best to keep the keys in an array, iterate over the array and extract the values with a hash lookup.