Thanks to people on the Japanese mailing lists, I've learned that iso-2022-jp should be used for mail and news because it uses 7 bits instead of 8. For some reason, my Emacs defaulted to euc-jp. Fixed now with the handy snippet
(setq mm-coding-system-priorities '(iso-2022-jp iso-2022-jp-2 shift_jis iso-8859-1 utf-8))
Don't worry about M-x describe-coding-system not saying that the buffer will be in iso-2022-jp. If you have
Coding system for saving this buffer: = -- emacs-mule
it will try iso-2022-jp first.