I just read this entire thread, and would like to offer my two cents.
I have been converting videos for years from one format to another, for psp, ipod, Android, dvd playback, you name it, I've tried it. Here are my favorites for routers and converters:
IMO there is only one option: Handbrake, period.
If you look in the official handbrake forums you can find plenty of Android presets for download.
1. Any Video Converter
- Simple to use, comes preloaded with Android preset.
-Any x264 presets will work on Android phones, for smaller file size, use the psp preset
- link: Free Video Converter| Any Video Converter Freeware| MP4 FLV 3GP AVI MKV DVD Android Html5
2. SGI's Video Converter GUI
-Comes loaded with presets
-Completely free, available from SourceForge
-link: SGI's Video Converter GUI | Free Audio & Video software downloads at SourceForge.net
Try em out, they are awesome.