Since you know about MIME::Parser, you have MIME-tools (that's where MIME::Parser comes from). The documentation for MIME-tools gives examples for decoding and encoding MIME-formatted messages. All you need is a compression step in the middle. Have a look at Compress::Zlib.

Now try this out and if you have problems, come back with sample code and a description of what works and what does not work.