jettero,
Time::Local does some internal caching so subsequent lookups in the same month should be really fast assuming your dates are all being parsed within the same instance of the interpreter. So then it is a matter of speeding things up as fast as possible:

# Keep the lookup table in highest scope necessary to avoid create/des
+troy each time needed
my %lookup = ( Jan => 0, Feb => 1, ... );

#Assume unpack is faster than regex (Benchmark.pm to be sure)
# Add code to handle year appropriately
my ($mon, $day, $hr, $min, $sec) = unpack('A3xA2xA2xA2xA2', $date);
$mon = $lookup{$mon};
my $stamp = timelocal( ... );
[download]

Sorry this is just an outline, I am off to the aiport and had to hurry.