I agreed to take on a couple of work items at the OpenPGP meeting in Oslo,
Norway. One of those work items was to enumerate the MUSTS in RFC2440 in
order to help vendors begin conformance testing.
Just grepping for "MUST" won't get you anywhere. You missed important
specifications like "An OpenPGP message is a packet or sequence of
packets that corresponds to the following grammatical rules" (10.2)
and the key format requirements. On the other hand, some MUSTs just
describe facts where there are no possible choices on the
implementor's side and one might as well write "the octet is 5", "the
packet is ignored", "the flag is zero".
But there are more problems to it. If you really want to take this
task upon you, you'll have to do what the authors already should have
done before publishing a standards track RFC: look at each feature the
RFC describes and determine whether or not it is required for a
minimal implementation.
There are contradictions in the RFC:
"Hashed subpacket data. (zero or more subpackets)"
^^^^
"Signature creation time [...] MUST be present in the hashed area."
The issuer key ID subpacket is never specified as a required, but
later on in the section "Subpacket Hints" the RFC mentions in passing:
"An implementation SHOULD put the two mandatory subpackets, creation
time and issuer, as the first subpackets".
The RFC doesn't say anything about accepting V4 signatures.
Much of the complexity of OpenPGP comes from the desire to be
interoperable with PGP 2. But the RFC does not even mention that PGP 2
expects certain packet length types for certain packet types.
Similarly, PGP 5 requires certain packet versions for certain
signature types. This sort of thing ought to be described in an
implementor's guide.
By the way, you forgot "MUST implement Elgamal" in your list.