メールの文字化け

MacとWindowsでのメールやり取りで、本文が文字化けを起こしてしまいます。
対処法をご存じでしたら是非ご教授下さい。

こちらが使用しているのは、MacOSX、バージョン10.4.8で、メールは付属のソフトを使っています。
テキストエンコーディングは自動の設定です。
文字化けを起こすのは先方がWinの場合です。
対策も含めて事例を書きます。

事例
1　MacからWin→文字化け
2　Winからのメールを受信（読める）、そのメールに引用文付きで返信→文字化け
3　引用返信で文字化けしたので、新規で送り直す→文字化けなし
4　Macから自社内Winへメール送信し、それを先方Winに送り直す→文字化けなし
5　Winでも問題なくこちらと送受信できているクライアントもいます

こちらの設定というよりも、受信側の問題なのでは？とも思うのですが、
どちらにせよ解決策を先方なりに知らせる必要があります…。
よろしくお願いします。