(the return leaving the hash's iterator in the middle so that repeating the call to foo gives different results) the same problem exists without the return statement: sub foo shouldn't make unwarranted assumptions about the iterator, so should do a void-context keys %$hashref; before the loop.

Also a possible problem is the call to frobnicate; what if it also does something to affect the iterator of the hash passed to foo? If that's a possibility, you'd need to fetch all the keys up front (or use the lexical-iterator suggestion made by someone else in this thread).