iPhone hacker "core"'s latest version of ffmpeg will convert a wide range of video formats to iPhone-compatible formats.
If you decide to do this, be aware that it will take forever and run hot, and we still don't know how to change the clock rate to make it go faster. Make sure your iPhone is well ventilated and plugged into a power-source for the duration. Also run your conversion with nohup so that when the iPhone goes to sleep (because you know it will) it won't kill your conversion process like it did with mine.
So is there a point to converting videos on the relatively underpowered iPhone? Well, no, really there isn't. Sometimes it's just enough to know that you can.
Here's an example of the syntax:
ffmpeg -i AVI_DivX.avi -f mp4 test.mp4