It is less of a problem if you plan to encode files to fit the resolution/power of the device, as you can make them in such a way that they will conform to the power of the Kaiser in order to deliver smooth playback (ie around 600kb/s in QVGA). This can still provide a decent quality, especially on a qvga 2,8" screen (which wouldn't use a VGA resolution anyway). But don't expect to watch them on a laptop!
Has anyone benchmarked other video formats? While naturally most people would prefer to use DivX, I personally wouldn't mind recoding to MPEG (I'm not an expert with video formats but isn't MPEG compressed lighter than DivX - therefore less work for the processor + GPU?)