Hmm, I thought the x264 video encoder in MediaCoder was all CPU......
Anyways, while I haven't tried disabling CABAC in Handbrake for encoding (for one reason, playback had no problem with encoding on that, but converting the MKV stopped prematurely), I did try something different with MediaCoder, and that was trying a different Preset. By default, it was set at Medium. I set it to Ultra-Fast (which disables CABAC, though the settings page did not reflect that, I had to check with MediaInfo after the conversion), which encoded about 4 times faster at the expense of a little less quality and gaining about 1.5GB on the final filesize. The video, however, did play just fine on the Wii U with no seeking problems, so it would seem it can only handle so much, though I am perplexed how that can be the case when seeking would cause the problem while playing from start to finish with no seeking wouldn't. Makes me think that while CABAC contributes to the overall problem, I think something else might be contributing to it too (since converting with Handbrake + CABAC enabled did not have problems).
I'm currently attempting the Fast preset (73% done atm), which is between the Ultra-Fast and Medium presets. It does have CABAC enabled, but might have other features disabled. I'm also waiting for responses on the official MediaCoder forums, to see if they have any insight on this.
edit:
Just tested the transcoded version using the Fast preset on the Wii U, and I have yet to experience the problem within the 5 minutes of playback testing after seeking. Will do an extensive test in the morning. Quality was even less dissimilar from that encoded with Medium, and filesize is just about the same as Medium as well. If I continue to have no problems with this preset, then it'll likely be what I use for encoding Wii U videos from now on.
Thanks for your help.