"I think you're assuming that each e-mail will begin with '^From: '"
Actually, no. /^From:/im performs a case insensitive multi-line match. The ^ anchors the start of any line (and is unaffected by setting $/) so the match will find "From" and the start of the string or at the start of any following new line delimited "line". Try taking the sample code I provided reorder the header line, add new header lines, whatever takes your fancy so long as you don't add bogus blank lines before the "From" line.
Another useful link may be perlretut. There's a lot of reading there, but it will be worth the time working through it!
True laziness is hard work