While Mail::Internet will permit you to manipulate ordinary emails, if you want to deal with attachments or foreign characters, you will eventually have to descend into the world of MIME.
Due to the complexity of MIME messages, the MIME-tools package can get confusing. You will likely find yourself bouncing between three or four different man pages/PODs to get where you want to go.
Creating a MIME message is quite easy, and involves the MIME::Entity module (included). You simply call the build method to create the base message and then repeatedly call the attach method to add on parts.
Decoding an incoming message is more complicated. In Mail::Internet, every message has a header and a body. This is no longer true in the world of MIME. If the message is single-part, MIME-tools will return a header and a body handle (the change allowing easier access to binary files). However, in a multi-part message (one that has attachments), the body does not exist as far as the package is concerned. Instead, you have to look at the ->parts of the message, each of which has a head and a body (unless the part itself is multipart, in which case you'll have to recurse...).
There are a couple of convenience features that make life a bit easier. For instance, you can call the make_multipart method on all your incoming messages so that singlepart messages cease being a special case -- now you can use the parts method on it (iterating over the number of parts) to get the one or more parts that exist. If you have a multipart message that only has one part, there is a companion method to make_singlepart. Both of these methods behave gracefully when given inappropriate input.
Good: The modules provided manage to handle just about everything you could want with MIME messages, and since HTMail and attachments are ubiquitous, few people can afford to assume that their mail can be handled by Mail::Internet.
Bad: The moduleset is definitely "heavyweight". If you can get away with MIME::Lite (receiving only), you will save yourself some development time, and of course, your code will be "lighter", as should be obvious from the name. You will also need another way to send the mail you have produced (either pipe it to /usr/lib/sendmail -t -i on a *NIX or use Mail::Sendmail or Net::SMTP). As mentioned in a comment below, the encoding/decoding is done in memory, which can be a limitation. MIME-tools does, however, save parts out to disk if they are long, so you only have to have one part in memory at a time. A caveat is in order here: if you're creating a MIME message and use the purge method to get rid of disk files, the module will (try to) unlink the original attachment. If it fails due to file/directory permissions, it doesn't complain, though.