I tend to prefer to compute strings that can be sorted using the "default" sort even for problems as complex as this:

chomp( my @strs= <DATA> );
my @sorts= map {
    if(  ! /^(.*)(\d\d)(.*)_(\Q$str1\E|\Q$str2\E)$/  ) {
        "3".$_;                     # Non-matching lines come last
    } else {
        ( $4 eq $str1 ? "1" : "2" ) # Sort on _$str[12] first
        . sprintf("%02d",99-$2)     # Next on digits (reverse order)
        . $1 . $3;                  # Lastly sort on middle strings
    }
} @strs;
return @strs[ sort { $sorts[$a] cmp $sorts[$b] } 0..$#sorts ];
[download]

This may be significantly faster than writing a complex "compare" routine to pass to sort if you have a lot of items to sort.

        - tye (but my friends call me "Tye")