I'm assuming you don't want to load the entire mailbox into memory at once, since spam can make even a few days of email pretty large. The following is a line by line interpreter of the format you gave, with test data:

use strict;
use warnings;

my $c; my $text = <DATA>;
while (<DATA>) {
    if (index($_, 'From') == 0) {
        process($text); $text = $_;
    }
    else { $text .= $_; }
} process($text);

print "\n$c messages total\n";

sub process {
    # Do whatever you do to each message...
    $c++;
    print $_[0], "\n";
}

__DATA__
From ???@??? Wed Feb 02 11:47:05 2000
Message-ID: <38968A8A.DBB01A7@earthlink.net>
 From: Someone <beepbeep@earthlink.net>
X-Mailer: Mozilla 4.6 [en] (Win98; U)

Message 1
From ???@??? Wed Feb 02 11:47:05 2000
Message-ID: <38968A8A.DBB01A7@earthlink.net>
 From: Someone <beepbeep@earthlink.net>
X-Mailer: Mozilla 4.6 [en] (Win98; U)

Message 2
[download]

Rather kloodgey, but it works. Just replace DATA with whatever filestream has the email file.