I think that if you want to work with attachments that Mail::Internet isn't going to be much help. Maybe the best course of action would be to find out why MIME::Parser isn't working for you. Is it possible that the message you're receiving doesn't comply fully with RFC822 standards?
in reply to Dealing with "Detachments"
Also, since I suspect you'll need a different method for getting your message from the mailserver, can you use Mail::POP3Client or Mail::IMAPClient to get the message?
If you can send me a sample E-mail I'll try a few things and let you know what I find. The process might take a few hours though since I'd probably have to wait until lunch to take a look at it.