This looks wrong to me:

sub FIRSTKEY {
   ...
   $iterator = 0 unless defined $iterator;
[download]

Tied hash iterators have a strange division of responsibility: perl's actual iterator on the tied HV is responsible for tracking whether FIRSTKEY or NEXTKEY should be called, and the tied class is responsible for determining which key should be returned next. This allows things like void context keys() or values() to reset the iterator without actually calling any tie functions. So FIRSTKEY should always start at the beginning.