I think parse-time-string's performance can be increased significantly
by the attached patch, which replaces `parse-time-string-chars' with
something more sensible.  This function gets called at least once for
every character of the date being parsed, e.g. ~100,000 times in a 3000
article gnus buffer.

I made a comparisons with 3000 dates extracted from mail articles like
this, which seems to suggest some improvement.  I hope that it is also
correct.

(progn
  (garbage-collect)
  (benchmark 100
             '(dolist (d dates)
                (parse-time-string d))))

status quo: 41.547726s (5.333477s in 28 GCs)
patched   : 10.132069s (0.389833s in 2 GCs)

-ap