Hi,

MIME::Lite seems to be just what you're looking for.

    use MIME::Lite;
    my $msg = MIME::Lite->new(
        From => $from,
        To => $to,
       'Reply-To' => $reply_to,
        Subject => $subject,
        Data => $body,
    );
    $msg->send('sendmail', Sendmail => '/usr/sbin/sendmail');
[download]

Update: I was asked how using MIME::Lite could help the OP. Well, it will add some additional important headers to the message, like MIME-Version, Content-Disposition, Content-Transfer-Encoding and Date. These will make the message look less like spam. The message in the OP did not have these headers. Some might be added by the MTA. In any case, it's vital to see why a system thinks the message is spam. Maybe the relay is in RBL or whatever.