When an unchecked menu item is first shown, it has no checkbox. When the menu item is checked, it shows a box with a checkmark. When it is then unchecked, it shows a box without a checkmark.
Hence menu items have 3 states: 1) checked 2) unchecked but was previously checked 3) never been checked
I get around it by creating them all as checked and then unchecking in code.