davido,
but unless a hash changes its keys, order does remain stable

From perldoc -f each :
Since Perl 5.8.1 the ordering is different even between different runs of Perl for security reasons

In your case, it doesn't matter because each run can have its own iterator.
You also prefaced that with but unless a hash changes its keys which you shouldn't do under most circumstances.

The problem is that perldoc -f each also says:
It is always safe to delete the item most recently returned by "each()"

So as long as all someone is doing is looking at the hash.... This is paraphrased from a /msg conversation between davido and I put here for everyone's benefit