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.