Assuming the entire "record" is held in a scalar:

use strict;
use warnings;

my $string = <<HERE;
There is a new voicemail in mailbox 11234567890:

    From:     "Unknown" <Unknown>
    Length:     0:13 seconds
    Date:     Thursday, January 19, 2006 at 11:35:01 AM
HERE

if( $string =~ 
  m/
    mailbox\s+(\d+):
    .+?
    From:\s+(\S[^\n]*)
  /sx
) {
  print "Match: mailbox $1, from $2\n";
}
[download]

It may be unnecessarily explicit about what it requires for anchors, but with this sort of thing it's probably better to leave as little as possible to chance.