Personally, I've always used Time::ParseDate for this. It understands pretty much every format I've tried.
Absolute date formats
Dow, dd Mon yy
Dow, dd Mon yyyy
Dow, dd Mon
dd Mon yy
dd Mon yyyy
Month day{st,nd,rd,th}, year
Month day{st,nd,rd,th}
Mon dd yyyy
yyyy/mm/dd
yyyy-mm-dd (usually the best date specification syntax)
yyyy/mm
mm/dd/yy
mm/dd/yyyy
mm/yy
yy/mm (only if year > 12, or > 31 if UK)
yy/mm/dd (only if year > 12 and day < 32, or year > 31 if UK)
dd/mm/yy (only if UK, or an invalid mm/dd/yy or yy/mm/dd)
dd/mm/yyyy (only if UK, or an invalid mm/dd/yyyy)
dd/mm (only if UK, or an invalid mm/dd)
Relative date formats:
count "days"
count "weeks"
count "months"
count "years"
Dow "after next"
Dow "before last"
Dow (requires PREFER_PAST or PREFER_FUTURE)
"next" Dow
"tomorrow"
"today"
"yesterday"
"last" dow
"last week"
"now"
"now" "+" count units
"now" "-" count units
"+" count units
"-" count units
count units "ago"
Absolute time formats:
hh:mm:ss[.ddd]
hh:mm
hh:mm[AP]M
hh[AP]M
hhmmss[[AP]M]
"noon"
"midnight"
Relative time formats:
count "minutes" (count can be franctional "1.5" or "1 1/2")
count "seconds"
count "hours"
"+" count units
"+" count
"-" count units
"-" count
count units "ago"
Timezone formats:
[+-]dddd
GMT[+-]d+
[+-]dddd (TZN)
TZN
Special formats:
[ d]d/Mon/yyyy:hh:mm:ss [[+-]dddd]
yy/mm/dd.hh:mm