The problem lies in the following:

while (my ($key, $value) = $array->each) { 
  last if some_condition($key, $value); 
}
[download]

If I exit the loop early, the counter doesn't get reset. "Fine", I thought. "I'll just mark my position with caller and if each() isn't called from the same spot, automatically reset the index."

This is normal behaviour. It happens with hashes as well, and has tripped up many a person who use each() in loops without resetting the iterator before they start. Ie:

#!perl -l
my %hash=(1..10);
sub printit {
    print join "\t",keys %hash;
}
while (my ($key, $value) = each %hash) {
    print "First: $key $value";
    last if $value>5;
}
while (my ($key, $value) = each %hash) {
    print "Second: $key $value";
    #printit;
}
__END__
First: 1 2
First: 3 4
First: 7 8
Second: 9 10
Second: 5 6
[download]

Unfortunately the documented way to reset the iterator is via perlfunc:keys or perlfunc:values, so you probably should special case the behavior of keys in void context to reset yours. At least thats what i do, as well as providing a method to reset.

But it should be clear, to be safe you need to reset the iterator before you start the loop and not after you have finished it as I have seen mentioned in another reply. In fact, each can be viewed as unreliable if any other code can operate on the item being iterated in the period between iterations. IE, if you use each() and you call a sub that can call keys or each() itself on the item being traversed expect an infinite loop as your iterator gets reset every time. (Uncomment the 'printit' line for an example... :-)