>>777 おめ。
要素の追加・削除に関しては、プログラミングperl第３版 p835 のもうちょっと下を読めば
『each 関数などによって繰り返しを行っている最中に、ハッシュに対して要素を追加したり削除したりした場合、その動作は保障されない』
とあるので、順番が保障されない以前に、each 反復子をあてにしてる状況では、要素の追加・削除はやっちゃいけないっぽい。

>>775 (関連して >>776)
each 反復子のリセットのためだけに values %hash や keys %hash を呼ぶのは時間効率・空間効率の点でどうか、と思わないでもない。
いや、each の実装次第だとは思うので断定はしないけど。(作成されたリストが内部的に保持され、有効活用されるのかも知れないし。)
一つのループ内でハッシュの全要素にアクセスするんなら、each なぞ使わずに
　foreach (keys %hash) { ($key, $value) = ($_, $hash{$key}); ... }
とかでどう？