Hola
En el primer caso, ¿estás grabando el CD como un disco de datos normal en el cual metes sólo el archivo MPG? Si es eso, esa es la causa de que unos reproductores lo lean y otros no. La estructura de un VCD es la de las carpetas que indicas en el segundo caso...
El mismo Nero te la hace, para eso tienes que tener el vídeo en MPG y crear un nuevo CD de Vídeo. En la ventana donde seleccionas CD de Vídeo, acuérdate de desmarcar la casilla "Crear CD conforme al estándar" ya que el MPG que haces no es estándar.