Have you tried to implement one? :-) I worked with a team who did a full implementation from scratch (commercially), and I optimized some parts for certain architectures.

The problem is not in getting the output. The reference decoder decodes just fine. The difficult part is getting the output on time, e.g. getting you decoder to run fast.

The reference decoder has not been designed for speed, and getting things to run fast requires architecting everything very differently: it's not just a matter of applying micro-optimizations to reference code.

Also, the "intermediate results" might be different for each decoder architecture, so you can't really rely on the reference code for those.

So yes, while testing is indeed easy, writing a fast decoder is definitely not a "step by step optimization" process. I'd bet every performant decoder out there was rewritten almost completely at least twice.

Which are the fastest freely available decoders available, no necessary open source?

Is it really deterministic mapping from input to output, for given configuration options? I imagine you can build different algorithms that choose what data can be removed, with different tradeoffs between encoding time, decoding time, memory consumption, output file size and experience of quality.

Decoder is completely deterministic. In fact the normative part of most MPEG standards is implementation of the decoder in C-like pseudocode (which is horribly slow because it is not optimized in any way and mostly deals with discrete bits).

On the other hand how encoder works is not specified at all apart from the obvious requirement that it has to produce something decodable by the above mentioned decoder.