I could see the menu item in AOT > Menus but when I opened the element I got this error message:
I knew that the Menu Item in question had a CountryRegionCode property set to Denmark (DK)
So, what was the problem? I could confirm that it had something to do with the CountryRegionCode by doing some tests.
With AX 2012 the controlling party is defined by the organization model. "If the country context of the controlling party matches the country context of the controlled entity, the functionality or UI elements will be enabled." (MSDN-article "Applying Country Specific Functionality [AX 2012]")
So the country region code of the primary address of the legal entity defines the country/region context for the controlling party - which means that if there is no primary address or the primary address is not in the same country as the menu item, the UI element will not be shown.
The resolution was to check if the Legal entity had Denmark as country code for the primary address:
Open the Legal entities form:
Once the primary address' country region was edited back to Denmark, the menu item appeared again.