Hola buenas.
Con el programa Total Video Converter yo convierto cualquier video (mkv,mpeg4) a xvid y se ven de miedo.
Lo que tienes que tener en cuenta es que a la hora de comprimir has de poner resolucion personalizada:
Para videos 16/9 has de poner una resolucion de 720x405 (La pantalla del omnia no es exactamente de 16/9)
Y apra videos 4/3 pues 640x480
Espero que te halla servido de ayuda. Un saludo.