Ok, I'm working with this under the assumption that it is safe, even desirable to throw away parts you can't change. eg sound, archives, rtf, or html. If that is the case the problem becomes 'How do I make a message with containing only text/plain from a message which may contain any type'. This can be broken down into 3 parts 'Find all the text/plain parts', 'Edit them', 'Put all edited parts back in the body'. I think you have the 'Edit them' part covered basically which leaves us with two things to do. so let's tackle the first:

There's two cases I see, a body containing one thing (hopefully text/plain) you already know how to handle this right? the other case is a body containing 'multipart/mixed' or 'multipart/alternative' which are pretty much interchangeable for us. In this case we can break it down to 'get each part inside the multipart', 'look at each part', and 'save for editing if part is text/plain'. I think this code should show my basic idea.

my @parts;

if ($msg->is_mime) {
    my @t_parts = $msg->parts();
    while (shift @t_parts) {
        if ($_->mime_type eq 'text/plain') {
             push @parts, $_;
             next;
        }
        if ($_->mime_type eq 'multipart/mixed' ||
            $_->mime_type eq 'multipart/alternative') {
             push @t_parts, $_->parts();
        }
    }
}
[download]

then you just edit each item in @parts. and assemble a new message with the headers from the old one and a new body containing whatever parts you have edited. If there is only one piece then the message content-type is 'text/plain' if there is more than one piece the type is probably 'multipart/mixed'. You will probably have to be aware of multipart/alternative with multiple text/plain inside, but that case isn't very likely. As for messages that don't contain any text/plain... it's probably spam or hotmail/yahoo. You may find that you need to capture the text/html parts, but that should be relatively easy to add.

an alternative strategy might be basically the same thing but instead of saving the text/plain parts delete anything that isn't text/plain or a multipart containing a text/plain. This way you don't need to worry about which multipart a text part was supposed to go into. I believe it is legal to have a multipart/alternative with only a single part inside it.

As for making sure the message is reconstructed properly.. that's why you are using Mail::Audit and MIME:Entity in the first place :). I hope that helps you some. and note I haven't tested any of the code. _{as a side note if you really want your code to say DWIM check out Acme::DWIM} :)