The best solution is to abandon the idea of giving the Labels menu item two different scopes (global versus selected objects) that depend on the context. I anticipate this will provide loads of opportunities to confuse the user, as you’ve already determined. Essentially, the proposed logic introduces an obscured mode, which is a classic source usability problems. You need to decide if it’s better for the users if label visibility is a property of the display or the object.
Object Scoped vs Global Scope
You provide the greatest flexibility if label visibility is scoped to the object and thus the Labels menu item always affects the current selection. Users can select or multi-select whatever needs a label, and if they want it for all objects, then they first do a Select All. The one extra step to hit Ctrl-A (for most platforms) will probably net out to less work for the user than having them repeatedly select the Label menu item in a frustrating attempt to persuade the application to show what is wanted.
On the other hand, maybe users don’t need that kind of flexibility, and the Labels menu item should always have a global scope. Maybe it’s enough to either have the labels on or off for everything. When the labels are off, maybe you can show the label for a given object on mouse-over, eliminating the need for showing labels just to identify one object in a cluttered representation. Maybe the developers need to work harder on the label positioning algorithm to prevent overlaps so users don’t have to suppress labels for certain selected objects. Scoping the Labels menu item to the selected objects shifts the label management burden to the users, perhaps adding a lot of select-this-and-that work that they rather not do.
Controls for Object Scoped
Having separate Show Labels and Hide Labels menu items is normally the best solution when the menu items are scoped to the selected objects. This makes it fast and unambiguous to change the label state of a multi-selection when some objects in the selection are showing labels and some are not. However, you say there are “many different label types,” which I take to mean that you have multiple Label menu items, and you don’t want to double the number by having Hide and Show menu items for each.
If you go with a single menu item per label type, you could show a “mixed state” checkmark (it it exists for your platform) when a selection has objects with and without visible labels, but then the user can’t tell what will happen when the menu item is selected.
Alternatively, you could with “majority rule” and shows the checkmark if half or more of the objects are showing labels. The action is determined by the state of the menu item (e.g., all hiding labels when a checkmark is shown); the action should not "toggle" the labels, hiding those shown, and showing those hidden. The assumption here is that if users bothered to select a bunch of objects, they want the one command that affects the largest number of the objects. Of course, some users might be confused when the state of the menu item doesn't match some of their selections, even when it's the minority, but that's the price of not having separate Hide/Show commands. Either approach may be good enough if mixed-state selections are rare.
If not, then you may want to reconsider having explicitly separate Hide and Show capabilities. One way is by a cascade menus (View – Show Labels > , and View – Hide Labels >, which each cascades to list all the labels). Another way is to have View – Labels open a dialog box listing all the label types as checkbox controls. Default checks can be set by majority rule (as a command dialog, perhaps this is less confusing than using checkmark menu items). Cascade menus are best if the users usually only hide/show one label type; the dialog is best if users usually hide/show multiple label types at a time.
Multiple labels types scoped to the objects is an inherently complicated UI, and you may be causing more confusion that you resolve by trying to hide this complexity behind fewer commands. It may be better to have a couple big hairy cascade menus or a dialog box so users know exactly what they’re getting into.
Simplify
Or it may be better to reduce the complication. Maybe the current multi-type label design is once again shifting too much label management burden on the user. Unless the users are preparing the view for two-dimensional imaging for a formal presentation, I’m inclined to believe that managing the label appearance is not the user’s primary task. The primary task is to manage the objects (create, monitor, update, associate, remove, duplicate, etc.). While they may say they want all this control over their labels, you may find in usability testing that they behaviorally don't bother to fuss with it at the current level of detail you provide, instead making minimum changes only when they absolutely have to. If so, you should consolidate your label types, firstly by user role (maybe set in Options/Preferences), and secondly by the tasks the labels are used for (set in View).
Maybe what the users really want is to see as much labeling detail as can be legibly shown. Maybe it’s better to automatically label whatever you can without overlapping any labels for the given view, perhaps giving precedence to foreground objects so users can intuitively pan, rotate, and zoom to see labels for objects they need to see (and there’s always the mouse-over trick). To account for differences in users and task, maybe all you need is a single No Labeling – Full Labeling slider control in the toolbar that users adjust until they see the level of detail they want in the window.
