Content-typeが問題ないんだったら、base64エンコードされたtext/html
パートが本当にShift-JISになっているか確認してみたら？
なんとなくUTF8とかUnicode系でデコードされているにもかかわらず、
Content-typeがShift-JISと間違ったものを付けている気がするけど

iPhoneでHTMLメール返信するとtextパートはオリジナルのエンコード、
なぜかHTMLパートはUnicodeでエンコードするという謎仕様で、
M$系のメーラがHTML表示すると文字化け、しかも全滅状態って
事例がある。M$はHTMLパートのエンコードをテキストパートから
拾ってそれでデコードしてしまいHTMLパートのContent-Typeを
無視する仕様になってる。M$米国のサポートではひそかに修正パッチ
でてるけど。

ちなみにOutlook系で文字化けせずQmail3だけで文字化けするなら、
単にOutlookのバグでたまたま表示できただけで、Qmail3は指定された
Encodeをその通り表示しているという正常動作の可能性あるよ。
HTML表示のときにQmail3でエンコードを変えて表示させたら文字化け直んない？
utf-8が怪しい