Bueno después de las 1300 soluciones que se han comentado en este hilo (y en alguno más), para los que os sigan dando problemas tantos "lios" de codecs aquí tienen otra alternativa:
The Kmplayer, es un programa para windows (no confundir con Kmplayer de linux) que tiene inegrado todos los codecs que hacen falta para ver los mp4 y lo que se te ponga por delante. Es completísimo (quizás demasiado), aunque en principio no hay que tocar nada, lo instalas te vas al video que quieras abrir y listo.
Esto lo he puesto en el hilo de Paradise Kiss, lo pongo aquí también para la gente que tenga problemas y no quiera instalar codecs.