Tengo una Nikon de 4 Mpx y los clips de video que hace no tienen una calidad aceptable para mi gusto, aunque lo hago en calidad máxima ¿alguien sabe si esto tiene que ser así?

Pues me imagino que si, normalmente esas camaras utilizan un formato de compresion especifico para que se pueda almacenar mas tiempo en la tarjeta de memoria pero aunque esté a máxima  calidad, no llegan a darte los 352x288 necesarios para tener una calidad tipo vhs.

Exacto Mario.
Javiernager, de la misma manera que las videocámaras hacen fotos mediocres, las cámaras de fotos graban video de manera mediocre. He visto algún modelo de videocámara que ya hace fotos a 3 megapixels pero aún no existe el "aparato perfecto" que grabe a una calidad aceptable y saque buenas fotos... supongo que comercialmente no es interesante para ellos. Les sale más rentable vendernos 2 máquinas que una sólo que haga dos cosas.
Supongo que algún día estará a la venta algún artilugio que grabe, haga fotos, sea teléfono, GPS... y todo con una calidad decente.