[creedo]

You might also try different codecs, some decode more easily than others. I haven't seen the latest divx used to encode anything lately, people seem to either use older divx or xvid, or they've moved on to newer codecs like h264.

You might see if you can encode to an xvid video/mp3 audio and see if it plays any better. Also just for fun try an h264 video/aac audio. H264 is more processor intensive to decode but I'm thinking phones might have hardware optimized for it since it's the common codec for 3gp videos. I know many computer video cards come built in with stuff to handle h264 decoding efficiently, maybe the phone does also.