Lost access to execute all MMC based console applications (*.msc files)

Some Background

There's a web server; it's on a corporate domain and my domain account is in a group that belongs to the local Administrators group on that machine. At some point, and I haven't been able to pinpoint when (I believe it was after a reboot after some Windows Updates), we lost access to execute all *.msc (Management Common Console Document) files.

Cases

Just for illustration, here are the results of trying to access various applications.

1. Computer Management

   MMC cannot open the file C:\WINDOWS\system32\compmgmt.msc
   ---------------------------------------------------------------------------
   This may be because the file does not exist, is not an MMC console, or was
   created by a later version of MMC. This may also be because you do not have
   sufficient access rights to the file.
   

2. Internet Information Services (IIS) Manager

   MMC cannot open the file C:\WINDOWS\system32\inetsrv\iis.msc
   ---------------------------------------------------------------------------
   This may be because the file does not exist, is not an MMC console, or was
   created by a later version of MMC. This may also be because you do not have
   sufficient access rights to the file.
   

I have confirmed that each of those files does exist, and that it is an MMC console, and that I have sufficient rights to the file; the one that I don't know how to troubleshoot is the "was created by a later version of MMC" part of the error messages.

Here's the kicker: If I launch the MMC console manually (Run > "mmc"), I can successfully add each of the console applications above through the "Add/Remove Snap-in..." dialog and use them just as I would have if I had launched them manually. It's just when launching the *.msc file directly (or by shortcut) that we get the error.

Microsoft Management Console version:

Version 5.2.3790.3959 (Build 3790.srv03_sp2_gdr.101019-0340 : Service Pack 2)

The server OS is Microsoft Windows Server 2003, Standard Edition, Service Pack 2. If additional information or testing is recommended, bear in mind that I can do pretty much anything except log into that machine as the local Administrator account.

EDIT - Additional Resources

I poked around some more and came across these similar problems:

1. http://nabeelc.blogspot.com/2006/07/mmc-cannot-open-file-blah-blah.html

   The suggested solution is to reregister the msxml3.dll, but the registration fails.

Has anybody ever seen this before, or know where to start with troubleshooting? Any feedback is greatly appreciated.