At the moment I can't even encode MPEG-4 files with audio for playback on my phone...
You see my Nokia 3650 comes with the RealOne player which supports MPEG-4 ISMA Profile 0 but with the AMR audio codec only, not AAC.
The AMR codec is partly founded by the GSM group, hence the standard on all mobiles - and is optimised for speech - hence under the audio encoding options on Apple's Quicktime MPEG-4 encoder you can see the option "Speech" which is grayed out - that's for the AMR codec which is not supported yet.
The only way I can get MPEG-4 files I create with Quicktime to play on my phone, is to drop the audio all together, and the video plays fine on its own.
.3gp support is not that big a deal for me (it's basically H.263 video and AMR wrapped in a 3GP approved format) - Quicktime supports H.263 video, just not the AMR again.
AMR seems to be the gaping whole here, Apple have officially promised support for it in an upcoming release of Quicktime.
Rumors have it Quicktime 6.3 will add support for it, and it is due out very soon. I hope so, I'd like to see Quicktime seemlessly exchanging Video and Audio with my mobile, just as it does now with JPEG pictures.