Baja el Any Video Converter, tiene version gratuita, tesirve perfectamente.
Converti tu video a la resolucion de la pantalla de tu celular.
Usa el perfil MP4 para celular con el codec mpeg4. (no xvid ni x264)
Ahi solo mueves el bitrate de video (yo pongo 192) bitrate de audio (yo pongo 96) y los frames per second en automatico.
Listo, el video se vera con buena calidad en el celular y pesara de 8 a 16 Megas.

Tiene tambien para que le haga dos pasadas al video y la compresion-calidad sea mas eficiente