Well the first thing I'd do (just for maintainability and clarity)

        if ($in{'type'} eq "multipart") {
                 print MAIL "MIME-Version: 1.0\n";
                 print MAIL "Content-Type: multipart/mixed; boundary=\
+"----=_Next_Part_$boundary\"\n";
         }
         if ($in{'type'} eq "multipart") {
                 print MAIL "------=_Next_Part_$boundary\n";
                 print MAIL "Content-type: text/plain;\n";
                 print MAIL "charset=us-ascii\n";
                 print MAIL "Content-Transfer-Encoding: quoted-printab
+le\n\n";
         }
        if ($in{'type'} eq "text" || $in{'type'} eq "multipart") {
                 print MAIL "$text_message\n\n";
                         if ($in{'remove_notice'} eq "1") {
                                 print MAIL "-------------------------
+--------------------------------------------\n";
                                 print MAIL "Removal notice";
                                 print MAIL "$in{'subscribeUrl'}?$unsu
+bscribe&$in{'list'}&member\n";
                                 print MAIL "-------------------------
+--------------------------------------------\n\n";
                         }
         }
         if ($in{'type'} eq "multipart") {
                 print MAIL "------=_Next_Part_$boundary\n";
                 print MAIL "Content-type: text/html;\n";
                 print MAIL "charset=\"base64\"\n";
                 print MAIL "Content-Transfer-Encoding: quoted-printab
+le\n\n";
         }
         if ($in{'type'} eq "multipart" || $in{'type'} eq "html") {
                 print MAIL "$html_message\n\n";
                         if ($in{'remove_notice'} eq "1") {
                                 print MAIL "<BR><BR>";
                                 print MAIL "-------------------------
+--------------------------------------------<br>";
                                 print MAIL "HTML removaql notice";
                                 print MAIL "<a href=\"$in{'subscribeU
+rl'}?$unsubscribe&$in{'list'}&member\">$in{'subscribeUrl'}?$unsubscri
+be&$in{'list'}&member</a><br>";
                                 print MAIL "-------------------------
+--------------------------------------------<br><br>";
                         }
         }
[download]

becomes

my $msg = '';

my $multihead =<<EOMULTIHEAD;
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="----=_Next_Part_$boundary"
------=_Next_Part_$boundary
Content-type: text/plain;
charset=us-ascii
Content-Transfer-Encoding: quoted-printable
EOMULTIHEAD

my $multibound =<<EOMULTIBOUND;
------=_Next_Part_$boundary
Content-type: text/html; charset="base64"
Content-Transfer-Encoding: quoted-printable

EOMULTIBOUND

my $removal =<<EOREMOVE;
---------------------------------------------------------------------
Removal notice
$in{'subscribeUrl'}?$unsubscribe&$in{'list'}&member
---------------------------------------------------------------------

EOREMOVE

my $htmlremove =<<EOHTMLREMOVE;
<BR><BR>
---------------------------------------------------------------------<
+br>
HTML removal notice
<a href="$in{'subscribeUrl'}?$unsubscribe&$in{'list'}&member">$in{'sub
+scribeUrl'}?$unsubscribe&$in{'list'}&member</a><br>
---------------------------------------------------------------------<
+br><br>
EOHTMLREMOVE

$msg .= $multihead if $in{'type'} eq "multipart";
unless($in{'type'} eq 'html') {
  $msg .= $text_message; #XXX include the newlines in the message body
  $msg .= $removal if $in{'remove_notice'} eq "1";
}
$msg .= $multibound if $in{'type'} eq "multipart";
unless($in{'type'} eq 'text') {
  $msg .= $html_message; #XXX include the newlines in the message body
  $msg .= $htmlremove if $in{'remove_notice'} eq "1";
}
print MAIL $msg;
[download]

This seperates the wheat(code) from the chaff(mail), and saves on print statements (which *will* speed it up).

UPDATE: Damn, Ovid finished his reply first ;-)

--
perl -p -e "s/(?:\w);([st])/'\$1/mg"