If you're going to go to the trouble of two  s/// operations, you might as well go all the way to a GRT/decorate-sort-undecorate solution; then you can at least claim to be getting the maximum possible performance from the Perl sort built-in.

c:\@Work\Perl\monks>perl -wMstrict -le
"my %data = qw(
   Dec02 2  Jan02 3  May05 4  Dec14 8  Dec01 5
   Jan14 7  Apr05 6  Feb14 9  May15 10
   );
 ;;
 use constant Y_WID => 2;
 use constant M_WID => 3;
 my %mon_n = qw(
   Jan  1  Feb  2  Mar  3  Apr  4  May  5  Jun  6
   Jul  7  Aug  8  Sep  9  Oct 10  Nov 11  Dec 12
   );
 ;;
 my @sorted_dates =
   map unpack(qq{x${\Y_WID} x${\M_WID} a*}, $_),
   sort
   map sprintf('%*s%*s%s', Y_WID, $_->[1], M_WID, $mon_n{$_->[0]}, $_-
+>[2]),
   map [ m{ \A ([[:alpha:]]{${\M_WID}}) (\d{${\Y_WID}}) \z }xms, $_ ],
   keys %data
   ;
 ;;
 print qq{Key - $_  and b value - $data{$_}} for @sorted_dates;
"
Key - Dec01  and b value - 5
Key - Jan02  and b value - 3
Key - Dec02  and b value - 2
Key - Apr05  and b value - 6
Key - May05  and b value - 4
Key - Jan14  and b value - 7
Key - Feb14  and b value - 9
Key - Dec14  and b value - 8
Key - May15  and b value - 10
[download]

Update: See A Fresh Look at Efficient Perl Sorting by Guttman and Rosler (the G and R of GRT). Also: It seems to me now that all the regex sub-string extraction and sprintf-ing would have been much neater, clearer and more maintainable if encapsulated into a separate function. Oh, well...