Generally speaking, even if Perl were to give you the same output each time, I doubt it would be sage advice to count on what that order was in any way. Merely upgrading perl could give you a different set of answers (if Perl-5-Porters were to suddenly find a new magical algorithm that solved some issue of speed, memory, or both, for example). Which means that if you moved from one machine (running Perl 5.8.1) to another (running Perl 5.8.3, say), you could get different answers.

Thus, the answer has always been that if you need some sort of order to these keys, you need to impose that order yourself (via sort or Tie::IxHash or something). As lima1 says, they now force this good habit on you to reduce security exposure risks. But that doesn't change the fact that it was always a good idea.