dragonchild,
Well after seeing your update, it helped to clear up the problem. You were not going into the second level hash for deletes. I still don't understand why the second example should end up in 1 slot instead of 2, but I think this is right:

my $end = [];

for my $key ( keys %$start ) {
    next if ! exists $start->{$key};
    my @values = ($key , keys %{ $start->{$key} });
    push @$end , \@values;
    Eradicate( @values );
}

sub Eradicate {
    delete @{ $start }{ @_};
    for my $key ( keys %$start ) {
        delete @{ $start->{$key} }{ @_ };
    }
}
print Dumper( $end );
[download]

Cheers - L~R