Never been a big fan of ST ... it's kinda like a one night stand ... sure it feels good but you feel ashamed afterwards (or so I'm told). Just use temp variables ...

#!/usr/bin/perl

use strict;
use warnings;

my %hash =
  (  'foo00' => '12:NY:me@yoi00.com',
     'foo01' => '12:NJ:me@yoi01.com',
     'foo02' => '12:NV:me@yoi02.com',
     'foo03' => '12:AL:me@yoi03.com',
     'foo04' => '12:AK:me@yoi04.com',
     'foo05' => '12:MD:me@yoi05.com',
     'foo06' => '12:MO:me@yoi06.com',
     'foo07' => '12:MI:me@yoi07.com',
     'foo08' => '12:MA:me@yoi08.com',
     'foo09' => '12:CA:me@yoi09.com',
  );

# create array that looks like this
#  [
#    [ foo00, NY ],
#    [ foo01, NJ ],
#    ..
#    [ foo09, CA ]
#  ]
my @temp;
foreach my $key ( keys %hash ) {
  my @values = split( /:/, $hash{$key} );
  push( @temp, [ $key, $values[1] ] );
}

# sort array by second element
my @sort = sort { $a->[1] cmp $b->[1] } @temp;

# roll through sort and use
# first element of array as key into hash
foreach my $ref ( @sort ) {
  print "$ref->[0]: $hash{$ref->[0]}\n";
}
[download]

So ST is compact but too dense for me (or maybe I'm too dense for ST).