I use
http://www.dvdvideosoft.com/ "Free Video to iPhone Converter 2.1.1.3" which I have never updated since I first Downloaded and Installed it a few months ago when I first purchased my iPhone. I then convert my AVI/MKV/MP4 Video File that I would like to watch on my iPhone to the Quality Setting "iPhone High Quality (MPEG4, 30fps, 480x320; AAC - 192KBit)" and then use iTunes to Transfer that now iPhone Ready to Watch MP4 Video File to My iPhone.
I've had no problems since I first took home my iPhone 3G 2.28 and waited a very long time for that 2.2 Update, I haven't yet updated to the latest Firmware as I want to watch these forums to see if there are any other issues with this latest update, since I like the way my iPhone is currently working as it is giving me no problems at all with loading and performance.
Hope the DVD Video Soft program helps solve your Video Problems as it did mine!