rspence,
According to perldoc -f each, you should not add keys to a hash while you are iterating over it in an each loop.

It is also likely that you can get away with just one loop by using exists and/or defined. Since I couldn't figure out exactly what you wanted, I am providing the nested loop framework and leaving the reading of perldoc up to you to see if it can be shortened.

#!/usr/bin/perl -w
use strict;

my (%hash1, %hash2);    # Defined elsewhere in the program

for my $key_h1 (keys %hash1) {
    my $val_h1 = $hash1{$key_h1};
    for my $key_h2 (keys %hash2) {
        my $val_h2 = $hash2{$key_h2}
        
        # You can now check $key_h1/2 & $val_h1/2
        # And safely modify %hash1 or %hash2
    }
}
[download]

Cheers - L~R

Update: Abigaill is correct (as usual), but I was confused as to what rspence actually wanted.

Since the root node has been updated with clarifications, my post looks bad