in reply to Scoping problems with recursive function

It is as if the "each" somehow is like a "global" in that when I call the function recursively, it remembers at which value it was at and continues from there.

It is. Or rather, it's tied to the hash, so that it will always pick up where it left off anywhere. See each:

There is a single iterator for each hash, shared by all "each", "keys", and "values" function calls in the program; it can be reset by reading all the elements from the hash, or by evaluating "keys HASH" or "values HASH".

You probably want to use keys instead to iterate over it:

for my $key (keys %hash) {