You don't want to modify the body of the message at all. Use the existing content, completely unmodified (unparsed, etc, other than seperated into messages) as the message body, and use the new envelope-from and envelope-to in the SMTP transaction.

There is no reason to attempt to parse the message, unless there's some sort of information that you need to use to determine where to route the mesage to, if you really want it to be as close to the original as possible.

Now we come to the question -- do you really want it close to the original? If the mail program that's reading the messages sorts on the message's date, and not the received time of the message, this could cause some odd effects, as they might not realize that you've just inserted a couple hundred messages that were dated 3 years ago into their mailbox. Most modern mail readers don't have this problem, as they default to using the received time for their date sorting, but it's possible that this might be an issue.

Update: If people are going to suggest non-perl solutions, I might as well, too ... using pine, enable aggregate commands, and bounce command, then ;aab (or well, whatever selection criteria for the folder)