mp4 is clearly the new standard for video on these new gen mobile devices.
Most of my files (~3.5 TB worth) are all .mp4 or .mkv in 720p or higher... They run on the DX, but the bitrates tend to be overkill and performance is reduced. Truth be told these devices still cant handle decoding HD video at those higher resolutions, but I didnt expect them too..
I also found that most .AVIs that I have are not playing back in sync or smoothly, but most of them are 350mb for ~40 mins and if reencoded to mp4 i can half the file size with the exact same quality.
Just use handbrake to encode anything to mp4, check to make sure the extension is mp4 and not m4v and ur good to go.