Use a counter. So, you'd have something like:

elsif (/Message-Id:/) {
    $counter = 1 - $counter;
    print $_ if $counter;
}
[download]

Somewhere in the beginning, have my $counter = 0; and you should be fine.