If you haven't looked at in a while, you should try VP9 again. It is much faster, especially if you try the new 1.4.0 release candidate.

Also keep in mind that MPEG 4 includes two separate video codecs, ASP and AVC, with wildly different performance.