Rather than creating a compare function, I'd create a sort key generation function, and use the map sort map (Schwartzian transform) or the Guttman/Rossler method - (warning: untested, and if your 'any string' clauses contain two digits, then your hosed unless you come up with more constraints):

# You may want to wrap '\Q' and '\E' around each of $str1 and $str2
my $re = qr/^.*(\d\d).*_($str1|$str2)$/;

my @sorted = map { $_->[0] }
 sort { $a->[1] cmp $b->[1] }
 map { [ $_, sort_key($_, $re, $str1) ] } @list;

sub sort_key {
 my ($str, $re, $str1) = @_;
 my ($rule1, $rule2, $rule3) = ("1","00","1");
 if ($str =~ $re) {
  $rule3 = "0";
  my ($num, $s) = ($1, $2);
  $rule1 = "0" if $s eq $str1;
  $rule2 = sprintf("%2d", 99-$num);
 }
 return "$rule3$rule1$rule2$str";
}
[download]