プロファイルとレベル指定さえ正確にしてやればあとはサイズの問題だと思います。QVGAにしか対応していない機種があったりするので若干注意が必要。
品質ベースだと再生できないなどの問題もありますから、基本的にはCBRないしビットレート指定のVBRが望ましいです。マルチプレクサは3gpで出力し、プロファイルはベースライン(メインでもほとんどの機種で再生は出来ます)にするのが無難です。
Docomoの場合、比較的新しいものであればH264+mp4コンテナでも普通に再生は出来ますので、AviUtil+x264(オプションは少なめに)でも動画の作成には問題ありません。
例えばAdobe Media Encoder(CS4ですが、CS3以前でも同じ設定が可能)で出力した動画も普通に再生できます。
エラーですが、ピクセル数(特に縦が270等)が4の倍数になっていなかったり、音声が24bit wavだったりしませんか?
あと、速度に関してですが、デュアルコア以上だとさすがにマルチスレッド対応アプリに比べて劣る点は否めないものの、シングルスレッドとしては最も速い部類だと思います。オプション次第かと。