Just to check... Those videos do play properly with Quicktime Player, correct? It's possible that you have a bad, or non-Quicktime compliant, encode on that handful. iPods will only handle Quicktime compatible MPEG-4 (which isn't all of them because Quicktime only supports a subset of the profiles in the MPEG-4, Part 10 spec).
Also, if you use Windows Media Player, do they play?
Can you manually play them in MC by doing File --> Open and browsing and finding them?