This sometimes happens, which codec are you encoding with? xvid, divx or x264?
I had this problem with xvid once where everything I encoded would be the wrong size.
Try uninstalling xvid and downloading and installing another version.
There is something you can try to do first though to make sure the encoder is at least trying to use the right bitrate.
When you're at this step:
You see how there's the bitrate you want to encode at up the top right of the window?
Take note of that value, and when you click on the button that says second pass, manually put that bitrate into where it says Target Bitrate, (if you can, you can't do it for the first pass settings but 2nd pass you should be able to)
Something to try anyway, not sure how it will go.