@NEILMILLSTONE
Validation method works for me in Unity 2017.3.0f2

private const string MenuItemName = "Tools/SOMETHING";

public static bool Enabled
{
get { return EditorPrefs.GetBool(MenuItemName, false); }
set
{
EditorPrefs.SetBool(MenuItemName, value);
EditorApplication.delayCall += () => Menu.SetChecked(MenuItemName, value);
}
}

[MenuItem(MenuItemName)]
public static void ToggleEnabled()
{
Enabled = !Enabled;
}

[MenuItem(MenuItemName, validate = true)]
public static bool ValidateEnabled()
{
Menu.SetChecked(MenuItemName, Enabled);
return true;
}

Hello. After struggling with a similar problem (checkboxes lost after script compilation), it seems that I found a solution. You can call SetChecked in the MenuItem validation method. See documentation (https://docs.unity3d.com/ScriptReference/MenuItem.html) for more details about MenuItem validation implementation.

This is still an issue, since Menus cannot be checked during the game, we're left with checkboxes that always look unchecked in play mode. This makes people confused.

Even calling Menu.SetChecked(MENU_NAME, true) every frame doesn't cause a check mark to appear during play mode.