What a nightmare, but it makes me wonder: rather than decoding into micro-ops at runtime, could Intel or AMD "JIT" code up-front, in hardware, into a better bytecode?
I'm sure it wouldn't work for everything, but why wouldn't it be feasible to keep a cache of decoding results by page or something?