I did something like this a little over a year ago with Net::SMTP doing the deliveries. If I were writing this today, it would probably be a bit different, but here's what I had back then:

# $from is to be the envelope sender
# $msg is the full text of the message, headers and all
# (everything after the initial 'From ' line in the mbox
sub attempt_delivery {
    my ( $from, $msg ) = @_;

    my $smtp;
    my $success;
    my $sleepy = 1;

    while ( ! ( $smtp = Net::SMTP->new('smtp.example.com') ) ) {
        print "Sleeping $sleepy...\n";
        sleep( $sleepy );
        $sleepy *= 2;
        $sleepy = 60 if ( $sleepy > 60 );
    }

    if ( ! $smtp->mail( $from ) ) {
        $smtp->quit();
        return 0;
    }
    # in my script, $to is a global variable
    if ( ! $smtp->to( $to ) ) {
        $smtp->quit();
        return 0;
    }
    if ( ! $smtp->data() ) {
        $smtp->quit();
        return 0;
    }
    if ( ! $smtp->datasend( $msg ) ) {
        $smtp->quit();
        return 0;
    }
    if ( ! $smtp->dataend() ) {
        $smtp->quit();
        return 0;
    }
    if ( ! $smtp->quit() ) {
        return 0;
    }

    return 1;
}
[download]

I was parsing through my mbox files by hand, mostly because they were mangled in various unseemly ways. If yours are pristine, you'll probably want to check out Email::Folder::Mbox or Mail::Mbox::MessageParser or something. CPAN has many candidates.