iOS6の時もあったと思いますが、iOS7のiPhone5sで私が送ったメールが知人のアンドロイドケータイで文字化けしていました。

ちなみに私はSoftbankのiPhone5sです。

文字コードの問題だと思いますが、対処方法は下記の通りです。

設定メニューから一般をタップ

キーボードをタップ

キーボードをタップ

「新しいキーボードを追加」をタップ

言語は日本語以外なら何でもいいですが、ここではアラビア語をタップ

下図のように追加されたことを確認

設定メニューの「メール/連絡先/カレンダー」をタップ

署名をタップ

私の場合、既に以前の文字化け対応時に絵文字を入れていますが、それに追加で、アラビア語を一文字追加。縦棒が目立たなくて良いとAppleのフォーラムで語られていましたｗ

これで、署名に別言語で追記した文字が入っていることを確認の上、メールを送って見てください。多分文字化けが解消されていると思います。

必要なくなったキーボードは削除します。

キーボード画面の右上の編集をタップすると下図のようになりますので、追加した言語の左の赤いマークをタップ

「削除」をタップ

これで、一時的に追加したキーボードも削除されました。

キャリアが対応してくれるかもしれませんが、しばらくはこれで対処できると思います。