I'm working on a process that will work with all free conversion utilities that have more ability to optimize quality at the cost of timely conversion. Have mostly everything figured out, but recently got curious why I couldn't get mp4 wrapped versions of the stuff I have been testing to play in the stock player until I found this.
Android Supported Media Formats | Android Developers
It seems even though Tegra2 and OMAP4 and other newer processors can play High Profile H.264 really well, it's still not supported in the stock player. It seems I had read other places it was since Android 3.0, but seems that only H.264 Baseline is available to the stock player so far. I'm not done experimenting with different specific settings and 3rd party players yet, but am getting closer and will update on what I feel ends up with the greatest quality.
As an extra question for my experimentation, what file size for the videos do you consider reasonable? I am still trying to decide this based on what kind of quality it seems I can get out of some extreme compression. Even 1mbps when converted at extreme placebo pace is looking really good and ends up under 1gb files size for most movies. I am doubting it will work for really low contrast color gradients though, but haven't got enough content converted yet at the placebo pace to know for sure.
Oh, and the best 3rd party player on ICS I have found is MX Video. It will play some pretty extremely compressed files really well even in software mode when something with my file isn't working with whatever hardware accelerated regime it's trying and it's really quick and simple with it's UI to switch from hardware to software rendering. Also does the best I have found at going TRUE full screen smoothly after ui interactions.