nothing is actually broken in my opinion.

Famous last words. If all was sane, there would be no odd behaviour. I think that it is not necessary that the XS code itself uses each. It suffices that somewhere outside a hash reference is iterated, and XS code does something to this hashref passed into the XS which triggers hv_iternext_flags (defined in embed.h) or Perl_hv_iternext_flags perhaps via some macro.

Lets see...

qwurx [shmem] .../build/perl-5.25.10> grep hv_iternext_flags *.c *.h
hv.c:    while ((entry = hv_iternext_flags(ohv, 0))) {
hv.c:    while ((entry = hv_iternext_flags(ohv, 0))) {
hv.c:=for apidoc hv_iternext_flags
hv.c:Perl_hv_iternext_flags(pTHX_ HV *hv, I32 flags)
hv.c:    HE * const he = hv_iternext_flags(hv, 0);
hv.c:    while ((entry = hv_iternext_flags(hv, HV_ITERNEXT_WANTPLACEHO
+LDERS))) {
mathoms.c:    return hv_iternext_flags(hv, 0);
mro_core.c:    /* This is partly based on code in hv_iternext_flags. W
+e are not call-
perl.c:              while ((entry = hv_iternext_flags(dups, 0))) {
perlmini.c:              while ((entry = hv_iternext_flags(dups, 0))) 
+{
regcomp.c:        while ( (temphe = hv_iternext_flags(hv,0)) ) {
regcomp.c:        while ( (temphe = hv_iternext_flags(hv,0)) ) {
embed.h:#define hv_iternext_flags(a,b)    Perl_hv_iternext_flags(aTHX_
+ a,b)
hv.h:/* Flags for hv_iternext_flags.  */
hv.h:#define hv_iternext(hv)    hv_iternext_flags(hv, 0)
proto.h:PERL_CALLCONV HE*    Perl_hv_iternext_flags(pTHX_ HV *hv, I32 
+flags)
[download]

So hv.c mathoms.c perl.c mro_core.c regcomp.c are possible candidates. Since you also speak of a memory leak loosely coupled with your issue caused by the RE compiler, I'd start looking for code that calls functions from regcomp.c - but that's all just guesswork.

update:

This basic XS (created with h2xs -A Foo)

/* file Foo.xs */
#define PERL_NO_GET_CONTEXT
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#include "ppport.h"

MODULE = Foo        PACKAGE = Foo        

SV *
foo(hv)
    HV * hv
    CODE:
        hv_store(hv,"newkey", 6, newSVpv("foo", 3),0);
[download]

which just adds/updates a key/value pair to a passed hash reference reports the place where Foo::foo($h) is called:

use blib;
use Foo;
use Data::Dump qw(dd);
$h = {foo => 1, bar => 2};
while (($k,$v) = each %$h) {
    Foo::foo($h) if $k eq 'foo';
}
dd $h;
__END__
Use of each() on hash after insertion without resetting hash iterator 
+results in undefined behavior, Perl interpreter: 0x224f010 at foo.pl 
+line 6.
{ bar => 2, foo => 1, newkey => "foo" }
[download]

Without knowing what perl XS modules you are using inside your application, there's no way to tell where the error would arise from.

yes I agree that that was a bit vague. What I actually wanted to state was that assuming Perl is not broken for some other reason that the behavior of each() whatever it may be for a given circumstance under the condition of being called after an insert into the has is okay by me, I.E. I can live the possibly random pair of key/value returned.

"Sharing it would be very difficult for other reasons as well. Its sheer size, roughly 200k lines of source."

That's perfectly valid. Few of us here would be interested in wading through even a few thousand lines of code; certainly not 200,000 lines. In any event, that would far exceed the amount the site would let you post: I think the node limit is 64k characters. However, if you did track it down to some manageable code fragment, and provided that as an SSCCE, you'd be likely to get some positive feedback.

"It's been suggested that I somehow cut back on code until I find the culprit. This does not sound fun."

My suggestion of turning off the warnings was intended as an alternative to actually removing chunks of code. The idea would be to turn off warnings in parts of the code: when the warnings disappeared, that would be code you could investigate further. Obviously, without any knowledge of your code, I've no idea how useful or practical that approach might be.