Although, surely someone has taken a crack at validation with Parse::RecDescent or somesuch? I'd love to see it if someone's done it.

We were just talking about that in the CB. bart pointed out that Parse::RecDescent would probably be way too slow. Parse::YAPP might be better (see Re:x2 Easy Things (a plug for Parse::YAPP)) if you want a pure-Perl solution, but for speed there's no reason not to build a parser with yacc or bison or something of the sort and XS it.

Incidentally, I googled for an RFC822 yacc grammar (I can't believe that nobody's distributing one; it seems like the obvious thing to do) and came across this article. It's rather old, but probably still applies.