Not sure if the following code helps you but this is how I would have done it if I was not sure about the location of month in the string.

my $mons = {
    JAN => '01', FEB => '02', MAR => '03',
    APR => '04', MAY => '05', JUN => '06',
    JUL => '07', AUG => '08', SEP => '09',
    OCT => '10', NOV => '11', DEC => '12',
    JANUARY   => '01',  FEBRUARY  => '02',
    MARCH     => '03',  APRIL     => '04',
    MAY       => '05',  JUNE      => '06',
    JULY      => '07',  AUGUST    => '08',
    SEPTEMBER => '09',  OCTOBER   => '10',
    NOVEMBER  => '11',  DECEMBER  => '12',
};

my @dates = (
    '23 March 2009',
    '21st May, 2009',
    '2009, Jun 30',
    'Jul 09, 2009 at 05:03 UTC',
    'JAN 2 2009',
    'JAN 2 2009',
    '2  jan      ,       2009',
    '2009, 02-jan',
);

my @new_dates;
printf "[%25s]\t[%25s]\n\n", "orignal date", "new date";
foreach my $date (@dates) {
    printf "[%25s]\t", $date;
    # I have considered '\s,;:-' as separators modify the regex
    # if you have more.(ex add '/' for date format '08/Jan/2009') 
    if (my @matches = grep {$date =~ /(?:[ ,;:-]|^)$_(?:[ ,;:-]|$)/i} 
+keys %$mons) {
        # Line should match only one month, but just in case.
        foreach my $match (@matches) {
            $date =~ s/$match/$mons->{$match}/gi;
        }
    }
    printf "[%25s]\n", $date;
    push @new_dates, $date;
}

# OUTPUT
# [             orignal date]     [                 new date]
# 
# [            23 March 2009]     [               23 03 2009]
# [           21st May, 2009]     [            21st 05, 2009]
# [             2009, Jun 30]     [              2009, 06 30]
# [Jul 09, 2009 at 05:03 UTC]     [ 07 09, 2009 at 05:03 UTC]
# [               JAN 2 2009]     [                01 2 2009]
# [               JAN 2 2009]     [                01 2 2009]
# [ 2  jan      ,       2009]     [  2  01      ,       2009]
# [             2009, 02-jan]     [              2009, 02-01]
[download]

Though, I would say that solution by 'poolpi' looks short and nice.