Сам всё время забываю эти длинные командные строки, поэтому напишу сюда.

Вот как перекодировать видео для того, чтобы смотреть его на навигаторе (320х240 WinCE5):

mencoder -vf scale -zoom -xy 320 -oac lavc -ovc lavc -lavcopts \
acodec=mp2:abitrate=128:vcodec=mpeg4:vbitrate=400 \
-o outfile.mp4 infile.avi

Может, конечно, можно как-то поиграться и сделать в два прохода, или аудиокодек получше взять... Но это уже работает.