This has been a pain point for me as well in the past. I've come up with a couple of different solutions. The cleanest approach is to use an undocumented map event called optionschanged. Here is a code sample of how to use this:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<title></title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<script type="text/javascript" src="http://ecn.dev.virtualearth.net/mapcontrol/mapcontrol.ashx?v=7.0"></script>
<script type="text/javascript">
var map;
function GetMap()
{
map = new Microsoft.Maps.Map(document.getElementById("myMap"), { credentials: "YOUR_BING_MAPS_KEY" });
Microsoft.Maps.Events.addHandler(map, 'optionschanged', viewChanged);
}
function viewChanged(e) {
var options = map.getOptions();
if(options.labelOverlay == Microsoft.Maps.LabelOverlay.hidden){
alert("labels turned off");
}else{
alert("labels turned on");
}
}
</script>
</head>
<body onload="GetMap();">
<div id='myMap' style="position:relative;width:600px;height:400px;"></div>
</body>
</html>
This event fires when the labels on the map change, not when the checkbox is checked. I know this sounds confusing. If you are in automatic mode and check the labels nothing happens to the map as the labels only change when the Birdseye option is selecting as the map mode. Automatic leaves the labels on. However if you have already checked this box and then switch into birdseye/aerial then this event fires. It does what you are looking to do, just in a slightly different way.
As for this being an undocumented event, I'll speak with the documentation team for Bing Maps to see if they can add this.