update: lousy reading by me, the following tells you what you already know. Skip to next "update:"

each makes use of the iterator attached to a hash, so it knows which tuple to fetch next. The order of the hash keys is not really random, but randomized linear. While iterating over the hash with each, you change the hash by inserting new tuples. Where does this tuple end up? Farther up or further down the actual position? Should it be incorporated into the list you are iterating over? or exluded? Perl can't tell.

So the rule is: don't change a set while iterating over it.

The documentation states:

If you add or delete a hash's elements while iterating over it, the effect on the iterator is unspecified; for example, entries may be skipped or duplicated--so don't do that. Exception: It is always safe to delete the item most recently returned by each, so the following code works properly:

...

update: did you try adding use Carp; $SIG{__WARN__} = \&Carp::cluck to the code in question? That could give a clue.

update: nope, Carp::cluck doesn't get triggered. - The warning is in hv.c in Perl_hv_iternext_flags and only gets triggered if perl was compiled with PERL_HASH_RANDOMIZE_KEYS, and it shows up in a statically compiled perl or in libperl.so. It would be very exotic for an XS to roll its own Perl_hv_iternext_flags; but to make sure, you could

perl -pi.bak -e 's/without resetting hash iterator results/without res
+etting HASH iterator results/' libperl.so
[download]

and see if the message sports uppercase HASH in both cases.

If the each is called from an XS, and while being in XS context, there's no information available about the current file and line number, I'd consider that a bug in the internal error handler. It should report at least the shared library, and perhaps also go uplevel and determine the caller, and report that file and line number.