There are still a lot of unanswered questions about what you are doing & how, but this much seems evident:
You are not just forwarding original messages to their intended addressee, which is what redirect (or forward as original) is intended for. Instead, you appear to be acting as the addressee, receiving the message, somehow processing & potentially modifying it with something other than Mail.app to remove viruses, & sending that form along to the original addressee.
This is a substantially different situation from what you originally presented. If you modify a message before redirecting it (whether within Mail or with an external agent), Mail will very likely change its headers to accommodate the changes. For instance, if you remove an attachment, you may very well be changing the message from multipart to text, which will cause major changes in the MIME declarations. Even if you just add or remove a single character in the body of a plain text message, you are modifying it.
As I mentioned earlier, MIME does not require that a client app
encode a message in the same way it
decodes it. Not only is a different, equivalent encoding perfectly legal, it is generally considered a benefit if the encoding chosen is the most appropriate, efficient one for the content. For instance, if a message (or part) can be encoded as plain text in 7 bit form (US ASCII), or as some octet stream (like with
UTF-8), Mail is allowed to encode it as such, regardless of its original encoding.
Beyond these considerations, we must consider the (as yet not clearly detailed) effects of the mail server(s) on the message. An Exchange server is not necessarily MIME-compliant, since Microsoft has designed them to support proprietary features. Add client plug-ins or external processing of messages to the mix & it is very difficult to say what message in what format will eventually be delivered to the addressee.
Resolving this will most likely require the server administrator's participation & careful comparison of the original to the various sent & received forms of the message, taking into account the various MIME content types a message might contain & the equivalence of different forms, plus what (if anything) has been changed in the body of the original message before retransmission to the server.
The only thing that hints at a bug or problem with Mail itself in this thread so far is in the now removed source for the rule-driven redirect example you provided, since it seems to show Mail failing to include the encoding header for a plain text, utf-8 encoded message. However, since it isn't clear if this would be the case with other content types, or if the original was properly encoded to begin with (why base64 with utf-8?), plus the uncertainty regarding modifications, it is hard to say where the problem really is.
If you would like, I can suggest some tests that might help better clarify what is actually going on, but you should know that I cannot duplicate the stripped encoding header in my own redirect tests, so it is likely Mail itself is not the problem.