I was using Gom encoder to do my encoding. It free for 30 days and it stamps its watermark on the movie. Did fine with it, and had all the options i needed. However it seems that sometimes it cannot embed subtitle directly into the movie frame.
I use MenCoder to embed subtitles

But now i have found SUPER and i use it instead of GomEncoder.
If you want it, you should get it from their own site, because, and i quote

"It IS NOT RECOMMENDED to download SUPER © from other sites as you may get an outdated or tampered SETUP file.
This official web site is the ONLY one to provide the latest updated guaranteed virus-free spyware-free version of SUPER ©"

If you ask me, like the ones that created said, It truly does for free what other oncoders can't do for money.
It has EVERY codec you will ever need DIRECTLY embeded in the program itself. You can encode everything from everything, any format is recognized, it truly is amazing.

The one thing missing is the ability to embed subtitles in the video stream directly, hardcoded subtitles, like other like to name them.

It can even join files, etc you will see it has tons of option and it is easy to use.

I know i have found my right encoder.

Here it is:
http://www.erightsoft.com/SUPER.html