Thanks to the generous loan of a C750, I could start experimenting with software "enhancements".
After some research on the forums, I found there were many discussion about video playback on the C7/8x0, with most people using 320x240 only. Well, looks like you can do much better than that ! Maslovsky and kfetisov reported vga playback at 248 kbps with mono audio, but that too can be improved.
After some tests, I could succesfully achieve 640x352@25 fps, with 500 kbps and stereo 64 kbps audio. You simply have to overclock with CCCR=163 (edit /home/zaurus/Settings/freqchange.conf to add a line above the "Overclocked"/162 entry with "Max overclocking" and 163)
Here's the script I used for encoding, along with the command line for playback. I recommand mplayer-w100_1.0pre5.2-1_arm.ipk.
I put the files on a 1GB CF, so the space constraint is not existant. I will now try to reproduce that on a 2.6 kernel, which I patched to add overclocking support.