とりあえず問題の切り分けからかな。
自分の場合、
・ウイルス対策ソフトのメール保護機能がメールをチェックするためメールをデコード→再エンコードした際に文字化けしていた
　※送信側のメールヘッダに不備があり（あるフィールドが必要なのにメールに記述されていなかった）、それが原因で「不審なメール」として処理されていた
・HTMLの内容に不備があった（メールのエンコードとmetaタグのcharset属性が異なる、HTMLの構造がおかしい、どのバージョンに対応してるのかわからん、など）せいで文字化けしていた
⇒ウイルス対策ソフトメーカー／メール送信業者に、どこにどう問題があるのか詳しく報告、対応を依頼

てなわけで、さしあたりウィルス対策ソフトとかの常駐プログラムやメールのソースあたりを当たってみると、なんだかんだ原因が解るかもしれないよ。
それと、報告したら基本的には対応されてるよ。1件だけシカトこかれた業者があったけど（今どうなってるかは知らん）。