I'm pretty sure the version of mplayer I downloaded had mencoder.exe bundled with it. In fact, I didn't think mplayer would actually work without mencoder. I've had a look and I can't really see anywhere you can download mencoder.exe on its own, so I've uploaded it here.
Mencoder.exe
I've had problems with Movie Converter too - and even when it's at the top of its game it's still pretty slow. It seems that frontends that use mencoder - like Iriverter and CloneDVD Mobile - are a lot better for the job, although you generally have to fiddle about with the settings to get things just right.
Hope this works for you. If not, let me know.