Should be noted that the initial problem of the OP (short-circuiting a call-back) is easily solved with goto

Not if you wish to have the option of resuming the iteration; which I do. (Admittedly this was not mentioned in the OP.)

In addition, this suffers from all the same problems as throwing an exception to effect the early exit, which is (ab)using the exception mechanism for flow control.

Another reason for wanting an iterator is the ability to have multiple, concurrent, independent iterators; which is key to my application.

Last but not least is the avoidance of the nightmare that is Inversion of Control.

Think about how you'd have to restructure so many of your programs -- and how hard, if not impossible that would be -- if Perl's hashes only provided callback iterators. What a mess!