Not even my first gen Xbox is able to run .mp4 files very well so I try to avoid that encoding all together.
But if you think H.263, MPEG-4 is the way to go, I'll give this a try right now.