Create a hash of values. Here's some untested code:

my $values;
for $i (keys(%foo)) { 
    for $j (keys(my $fi = $foo{$i})) {
        $values{$fi{$j}} ||= [$i, $j];
    }
}
COMPARE: 
for $i (keys(%bar)) { 
    for $j (keys(my $bi = $bar{$i})) {
        my $c = $values{$bi{$j}} and do {
            print "match found: \$foo{" . $$c[0] . "}{" . $$c[1] . "} 
+eq \$bar{" . $i . "}{" . $j . "}\n"; # what makes you think I don't l
+ike interpolation?
            last COMPARE;
        };
    }
}
[download]