No sé cuánto dura la película Madagascar, pero sí se que en un VCD tan sólo entran los minutos de los que sea el CD, es decir, 74 minutos en los de 650 MB y 80 minutos en los de 700 MB, ya que un VCD no es más que un vídeo MPEG-1 a 352x288 y 25 fps (PAL) o 352x240 y 29.976 fps (NTSC) con un bitrate constante de 1150 kbps y una cadena de audio MPEG layer 2 a 224 kbps.
Si quieres meter más minutos necesitas hacerlo mediante los formatos XVCD (CVCD, KVCD...) que son como el VCD pero con bitrate variable, es decir, utilizan un bitrate más alto para escenas que lo requieren y más bajo para escenas que lo requieren menos (por ejemplo, una pantalla negra).
Ésto explica además que ese software lo comprima tan rápido, pues seguramente estás creando un VCD normal y corriente por lo que sólo hace el paso de recompresión, en cambio al hacer XVCD a parte de éste paso antes hay que hacer un análisis del vídeo para asignar los disferentes bitrates a las escenas del vídeo. Y eso, obviamente se traduce en más operaciones para el procesador, y más tiempo de espera para el usuario.
¿Software? Como ya te dije, yo utilizo
Avidemux porque me permite aplicar filtros a la vez que hacer la recompresión. También me han hablado muy bien de
VirtualDub, pero éste no lo he probado porque sólo está para Windows...
Saludos.