This sort is the only way I know to find the lowest value in my hash

Heh - finding the lowest value in a set (according to a given cost function) requires traversing the array only once - a sort not! I have not enough will to read what your code is doing exactly, but this should solve the specific ordering problem using List::Util:

use List::Util;

#... later in the code
sub IsStrongMatch {
    # Return true if id2 is only top ranked match for id1
    my $id1 = shift;
    my $id2 = shift;
    my $rC  = shift;

    for my $i1 ( keys %{$rC} ) {
        next if $i1 == $id1;
        my $href = $rc->{$i1};
        my $minid = reduce {
            $href->{$a} < $href->{$b} ? $a : $b
        } keys %$href;
        return 0 if defined $minid && $id2 == $minid;
    }
    return 1;
}
[download]

Untested!!!

Update: I realised that this answer is a little cryptic. reduce in List::Util allows you to visit each element in an array and do "something" based on the values you encounter along the path. What this code does (more or less) is probably best explained by mrborisguy in this post.