El problema no es el codec, es la resolución que suelen traer los videos y la potencia que requiere reproducirlos.
Los videos en mp4, además de usar unos algoritmos más complejos y costosos, suelen tener una mayor resolución lo que conlleva un coste mayor para reproducirlos.
Tanto el Geexbox como el MplayerWii pueden reproduccirlos, y aunque el primero tiene muchas más opciones, te recomiendo el MplayerWii pues su 'minimalismo' permite dedicar más potencia de la consola a la hora de reproducir consiguiendo que algunos videos de gran birate funcionen a una velocidad decente, lo cual no conseguirias con Geexbox.