Eto sucede en la mayoría de programas donde alteras los frames (en este caso con un logo incrustado), y debes recomprimir la película... Después de todo no es tan complicado...
Solo hay que saber:
Video Format (Formato de video, puede ser AVI, MPG, WMV...)
Video Codec (codec de video, depende cada formato trae sus codecs)
Bitrate (kbps, es la cantidad de información muestreada por segundo)
Donde mpeg4 es el tipo de video, el mpg4 solo existe en el formato AVI.
Codec es Xvid
Kbps es en este caso 991
Si fuera un mpeg1 o 2 la información cambia, pero no los diferentes rubros, y al recodificar debes seleccionar el formato/codec y ajustar sus valores...
si se te hace muy complejo podrías buscar algún soft mágico, pero solo es pasar valores, no creo que te de problemas