AFL might get significantly more code coverage than these test streams do because it actively seeks out more code coverage by observing the behavior of an individual binary on various inputs.

You could imagine a parser that deals correctly with every single one of the test streams and implements every single feature in the spec, yet also has an undetected exploitable vulnerability because it made an assumption about objects' sizes (which the spec permitted it to make, but which an attacker could take advantage of).

(On the other hand, maybe I don't understand enough about H.264 to appreciate a reason why this isn't possible in this specific context.)

So you're saying that a fuzzier would be more likely to hit every code path, that makes lots of sense when testing for vulnerabilities / crashes etc.

Validating against a spec is almost the opposite, since first it has to check that there is a code path for each part of the spec.

Right.

One extreme might be if you had a backdoor where the presence of a particular byte sequence in the input intentionally triggers some kind of malicious activity. The test streams can't detect this because they presumably don't contain that exact byte sequence, whereas something like AFL can find it because it can (potentially, depending on the nature of the test that recognizes the backdoor sequence) deduce what input would trigger coverage of that code path.