Take additonal care not to mess up encrypted or signed parts of the mail.

This. You (fgarpe) are onto a hiding to nothing.

I also agree with Perlbotics in that your users will become warning-blind and rapidly ignore it. If you absolutely must do this because the legals have insisted then I humbly suggest that you alter the Subject line only. Much simpler, no MIME involved, you just need to get the encoding right.

Good luck.