Claro que soporta MP4, con codec de video mpeg4 y audio aac. No se porque todos aun tienen sus videos en 3gp, este formato es de los primeros celulares que tocaban video.
Yo convierto con any video converter, la version gratuita casi no tiene limitaciones solamente no puede ripear de dvd y cosas asi, pero te convierte todo.

Arrastro mi video al programa.
Elijo el perfil "MP4 para telefonos moviles"
Elijo para video el codev mpeg4 (no x264 ni xvid)
Los frames per second veo que este en automatico.
Ahora solamente elijo los bitrates del audio y del video.
En el audio yo le pongo 96kbps y en video 192kbps (mas bitrate mas calidad, pero en celular no hace falta mucho bitrate, y si poner numeros altos seguro se lentea o ni toca)
Luego boton convertir y listo. Sale un archivo de 8 a 16M.
Convierto a partir de MKV, VOB, MPG, AVI, etc sin ningun problema.

Mi unico problema es en los archivos MKV que tienen el audio en VORBIS se desincroniza el audio. Pero extraigo el vorbis del video original, lo convierto a aac, lo vuelto a meter en el MKV y todo bien.