/.*?\n/ isn't really any slower, since it jumps to the closest newline it finds. The silly thing is the ? in that regex. The .*? in your regex WON'T match over the newlines, so you're missing an /s modifier I think. And since [^\n] IS ., I'd just write:

{
  local $/;
  my ($num, $from) = <FILE> =~ m{
    mailbox \s+ (\d+): \s+
    From: \s* (.*)
  }x;
}
[download]

Untested, but it seems to me that it should work properly, given the data from the OP.