my %lookup = do {
    my $i = 1;
    map { $_ => $i++ } qw( S M L XL );
};
my @sorted_values =
    map {
        $_->[0]
    } sort {
        $a->[2] cmp $b->[2]
            ||
        $lookup{$a->[1]} <=> $lookup{$b->[1]}
    } map {
        my ($x, $y) = /\w+:\s(\w+),\s\w+:\s(\w+)/;
        [ $_, $x, $y ]
    } @strings;
[download]

You made the same mistake I did. That's not a Schwartzian Transform (or at least not a proper one). The hash lookup should only be performed once per item being sorted, so we should be tossing the lookup within the first map being performed, rather than within the sort. Not to mention your sort is off now as you are sorting first by color then by size, when the OP wanted size then color. So we should really have something like this:

#!c:/perl/bib/perl -w
$|++;

use strict;

my %map = (
   S => 0, M => 1, L => 2, Xl => 3
);

my @sorted = 
   map { $_->[0] } sort {
      $a->[1] <=> $b->[1] or
      $a->[2] cmp $b->[2]
   } map {
      /^(\w+:\s+(\w+),\s+\w+:\s+(\w+))$/ ?
         [$1, $map{$2}, $3] : ()
   } <DATA>;

print join("\n", @sorted);

__DATA__
size: L, color: White
size: M, color: Orange
size: M, color: White
size: M, color: White
size: S, color: Orange
size: S, color: White
size: Xl, color: Orange
size: Xl, color: White
size: Xl, color: White
[download]