This is crazy that they made an iPod video and not all videos can be added, espc ones of the quicktime format.
Not so hard to figure out. QuickTime Player is a 22-23 MB package. Would you like to have the whole player taking up space on your iPod? I wouldn't. Apple simply restricted the iPod player's codec to read the current "state-of-the-art" formats best suited to a balance of video quality and compression and which was already compatible with audio that was already a part of the iPod. In effect the iPod only contains a sub-set of QTime's player abilities and therefore rejects all formats not compatible with its capabilities.
Since the iTunes player is based on or simply an extension of the main QT Player application, it can play the same files as the main player including those which will not sync to the iPod.
Having said all that, have you had any success yet? I note that you say you have MPEGs in iTunes. If true, they will have to be converted to iPod compatible files using a non-QTime based application which can handle muxed audio. As to the MPEG4's you mentioned, were they simply downloaded from the Internet and never converted specifically for iPod compatibility?