Thanks, your suggestion worked perfectly. If I add this, the data comes out correctly:
$str =~ s{euc-jp}{cp932};
So where are those labels coming from, anyway?
These mails are coming from hotmail. Just last week they started coming in as 'euc-jp?Q?' instead of 'euc-jp?B?', and the base64 ones were working fine. I don't know if hotmail changed something or if some email server or spam filter at my client's site might be altering the message. I've seen similar problems with the bodies of some mails from yahoo and hotmail before, where the charset is labeled as iso-8859-1 but it's really some Japanese or Korean encoding. Whatever else people might say about MS, Outlook does a great job of 'dwim' when it comes to email, for better or worse.