返事がついていないようですが、文字化けするのは本文だけなのでしょうか？サブジェクトが英語で本文が日本語、サブジェクトも本文も日本語などではどうなりますか？

日本の携帯がないのでこちらでは全く対応できませんが、それなりに一般的な利用上重要な気がするので、検証できるかたがいらっしゃいましたらよろしくお願いします。

ubuntu7.10
auにて実験
メール作成時のエンコーディングを「Shift_JIS」にすると文字化けなし
（半角英数、半角カナ、漢字、ひらがな、カタカナ）
それ以外だと、2バイト文字(漢字・ひらがな・カタカナ)が文字化け

デフォルトのエンコーディングはUTF-8になってます。

携帯電話で使える文字集合は携帯キャリアに依存しますが、あるメールを
受け取った時に文字化けするかどうか、は携帯電話の機種に依存します。

なので、情報を寄せて頂く場合は機種名（SO905とか810Tとかそういうの）を
添えて頂ければと思います。

チョット前（5年位）の記憶ですが、hitoさんの言われる通り、携帯のこの辺に関しては、携帯キャリア、タイプ、携帯メーカ、機種依存部分が多く、統一的に扱うのは無理だと思います。（最近は、チョット変わってきているようですが）
ちなみに、私は、W44Kですが、UTF-8のWebページは見れますが、UTF-8のメールは文字化けします。
結局のところ、「日本語メールは、ISO-2022-JPで」ということは今も変わってないのでは。