I'm told that someone once wrote an MPEG4 decoder that would dither the image down to 2-bit and size it to the player's display screen. It was never released publicly.

Hmm, that seems a bit out there. I think your mixing togther info from threads like this one talking about the StrongARM being capable of decoding MPEG4 video. It's such a demanding task on an iPaq, that I don't see enough power left over to dither it down/rescale it well.