"Must Not" or "May Not" - which is the most correct

I work in the IT industry and often read software and standards specifications that start with a section with definitions for certain words used in the document.

Recently I came across the following in section 1.3 of pdf document SSEK Version 2.0 by Andersson et al [verbatim except for added dashes]:

The keys words SHOULD, MAY, MUST and MUST NOT in this document are to be interpreted as follows:

SHOULD – This word mean that there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighed before choosing a different course.
MAY – This word mean that an item is truly optional.
MUST – This word mean that the definition is an absolute requirement of the specification.
MUST NOT – This phrase mean that the definition is an absolute prohibition of the specification.

The question is whether the last definition really is correct, or if it should have been MAY NOT instead to have the defined meaning.

Solution 1:

The problem here is actually may, not must (or must not). May can mean either optionality or regulation:

I may stop for groceries on the way home tonight.
May I have ice cream for dessert?

Your source is using it in the "optional" sense, not the "regulation" sense, so may not would also mean it's optional. Must not, on the other hand, always means that it is forbidden.

Here are uses that fit with those definitions:

I may stop for groceries on the way home tonight.
I must get gas before work tomorrow or I'll be stranded.
I must not run that red light.

Solution 2:

I would recommend reading the RFC 2119. They probably tried to abbreviate the definitions:

1. MUST This word, or the terms "REQUIRED" or "SHALL", mean that the definition is an absolute requirement of the specification.
2. MUST NOT This phrase, or the phrase "SHALL NOT", mean that the definition is an absolute prohibition of the specification.
3. SHOULD This word, or the adjective "RECOMMENDED", mean that there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighed before choosing a different course.
4. SHOULD NOT This phrase, or the phrase "NOT RECOMMENDED" mean that there may exist valid reasons in particular circumstances when the particular behavior is acceptable or even useful, but the full implications should be understood and the case carefully weighed before implementing any behavior described with this label.
5. MAY This word, or the adjective "OPTIONAL", mean that an item is truly optional. One vendor may choose to include the item because a particular marketplace requires it or because the vendor feels that it enhances the product while another vendor may omit the same item. An implementation which does not include a particular option MUST be prepared to interoperate with another implementation which does include the option, though perhaps with reduced functionality. In the same vein an implementation which does include a particular option MUST be prepared to interoperate with another implementation which does not include the option (except, of course, for the feature the option provides.)