Actually, it sounds to me like the sort() command is precisely what you need. Don't forget, you can define your own sorting methods.

In fact, this looks like a job for the Schwartzian Transform. First, you parse out all your strings at once, like so:

$string1 = 'foo';
$string2 = 'bar';

@in_strings = (
               'blue15midget_bar',
               'this is an exception',
               'blue17midget_foo',
               'deep13gizmonic_bar',
               'another exception',
               'red12dwarf_foo',
               'red12dwarf_bar',
               'exception containing _foo',
               );



%string_table = ();
foreach my $in_string (@in_strings) {
    if ( $in_string =~ m{(.+) (\d{2,2}) (.+) _ ($string1 | $string2 ) 
+$ }x \
) {
        $string_table{$in_string} = {
            initial => $1,
            number => $2 + 0,
            another => $3,
            ending => $4,
        };
    }
    else {
        $string_table{$in_string} = 'EXCEPTION';
    }
}
[download]

Next, you write a sorting routine that checks these parsed strings.

%end_order = (
    $string1 => 0,
    $string2 => 1,
);

sub funky_sort {
    my $p_a = $string_table{$a};
    my $p_b = $string_table{$b};

    if ( ($p_a eq 'EXCEPTION') && ($p_b eq 'EXCEPTION') ) {
        return $p_a cmp $p_b;
    }
    elsif ( $p_a eq 'EXCEPTION' ) {
        return 1;
    }
    elsif ( $p_b eq 'EXCEPTION' ) {
        return -1;
    }
    else {
        $p_a->{ending} eq $p_b->{ending} or return (
                                                    $end_order{ $p_a->
+{ending} } <=> $end_order{ $p_b->{ending} }
                                                    );
        $p_a->{number} == $p_b->{number}
        or return ( -1 * ( $p_a->{number} <=> $p_b->{number} ) );
        $p_a->{initial} eq $p_b->{initial}
        or return ( $p_a->{initial} cmp $p_b->{initial} );
        $p_a->{another} eq $p_b->{another}
            or return ( $p_a->{another} cmp $p_b->{another} );

        # If all of these are true, then the two are equal.
        return 0;
    }

}
[download]

Then, finally, you can use sort() to sort these guys.

foreach my $string (sort funky_sort @in_strings) {
    print $string, "\n";
}
[download]

And your stuff is sorted! See the manual entry on sort().

Disclaimer: I've tested this code to make sure that it runs, but haven't run extensive tests on it. Double-checks are appreciated and recommended.

stephen