I also recommend the "it's too frickin hard so let it be" approach. For most of the stuff I do, I allow the email to be semi-arbitrary and then if the user doesn't get his confirmation mail, etc, it's his responsibility. The UDP nature of email makes it ultimately impossible to trust 100% anyway, so I don't feel bad just handing the user input over to the mail stuff.
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.