Exchangeは文字種の判定が（ＭＳ曰く）「厳密」なので、
他のメーラーがいい加減な文字種指定をした場合に変換に失敗します
対策は
　１．他のメーラーに替える
　　　（私のやうに、Msn使ってると不可）
　２．MS-ExchangeClientをインストールする
　　　（ExchangeServerに添付のみなので、高くつきます）
　３．NKF.EXEなどで、変換する

NKFというソフトはEUC<->JIS<->SJISを相互変換してくれるソフトです
出所は覚えてませんが、VECTORあたりで見つかると思います