I think the Neo has potential as a video player even with the weak CPU it has right now (that's one of the things I do with my Palm TX). Come on, is anyone going to care if a 2.8" screen is displaying 240x320 or 480x640 video? You can't see a thing anyway ;-)
That said, the chief issue is making sure that the video is transcoded (scaled and pre-rotated) in advance, just as you outline. This *could* be done as a batch job invoked on the phone, or handled by whatever desktop app handles communication with the Moko. There is going to be some sort of app or function that does this transcoding.
Anyhow, I propose that a file extension be created (.mkv, for Moko Video), which is simply MPEG-1 at 240x320 or some resolution like that. This renaming would be done by whatever app did the transformation, and it becomes much easier to explain to grandma why her movie is running at 10fps.
Even if the movie player turns out crappy, you can still watch Charlie Chaplin vids at a resolution of 150x200 without panic.