Suppose you have a Win32 program with a checkbox. You just added it. No changes to message handler.

You click the box. What happens?

Answer: the box appears checked. Click it again, the box becomes un-checked. Riveting

Now suppose you have a Win32 menu item that is checkable. Again, added with no changes to message handler.

You click the item. What happens?

Answer: Nothing. It stays checked, if it was initialized that way. Unchecked, if it was initialized that way.

In both these cases, the item was added straightforwardly through resource script with no changes to the message handler.

Why are these two things different?

Explanation: apparently it falls out of broader Win32 design. The automatic-ness that the normal checkbox has, requires features to control it. For example, those checkboxes can be grouped into radio button groups with WS_GROUP. To add that same richness to menu items, too? You could, but it'd be an increase in complexity, and the benefit would need to be clearly justified. There'd need to be an "MF_GROUP" and all the API glue that comes cascading with it. Also, automatic checkbox-ness brings with it the chance of encountering errors, and errors tends to mean modal dialogs. It's okay to launch dialogs during normal window interactions, that happens all the time. But from a menu item? It would be really jarring and unexpected. Going more broadly than that it runs the risk of encouraging of bad habits: you might use the hypothetical "MF_GROUP" glue to do something strange and expensive, and that's not what menu items are for. Since it's not clear the benefit is justified, you're on your own for check state.

In case you were wondering, I'm not really trying to "sell" this inconsistency to you. I was just as surprised as you were. I am trying to explain it based on sources though. It's not random.

Something related- this docpage, "Using Menus - Simulating Check Boxes in a Menu". The sample code leaves you asking some broader questions of "why am I doing all this?"

Raymond Chen article fills in blanks: "Why can't you use the space bar to select check box and radio button elements from a menu?"

The design is also conveyed through Petzold's "Programming Windows, 5th edition" page 445 in the code sample "MENUDEMO.C". The message handler goes like

 case IDM_BKGND_WHITE: // Note: Logic below
 case IDM_BKGND_LTGRAY: // assumes that IDM_WHITE
 case IDM_BKGND_GRAY: // through IDM_BLACK are
 case IDM_BKGND_DKGRAY: // consecutive numbers in
 case IDM_BKGND_BLACK: // the order shown here.

 CheckMenuItem (hMenu, iSelection, MF_UNCHECKED) ;
 iSelection = LOWORD (wParam) ;
 CheckMenuItem (hMenu, iSelection, MF_CHECKED) ;

The general trend in this book is to leverage automatic facilities in the Win32 API wherever it makes sense to do. But here, the radio button-ness is all programmatic for checkable menus.