Looks like testing of SP1 may not have been as thorough as it could have been. Basically uninstalling the Vista service pack deletes one of the key internal queues that MSMQ uses and you will need to manually recreate it.

The Message Queueing service does not start when you run Windows Vista in Workgroup mode after you uninstall Windows Vista SP1

When MSMQ is installed, there are four private queues created by default when the Message Queuing service is started:

  • mqis_queue$ (Windows 2000 only)
  • admin_queue$
  • notify_queue$
  • order_queue$

These 4 queues represent the following files in %windir%\system32\msmq\STORAGE\LQS:

  • 00000001.xxxxxxxx (Windows 2000 only)
  • 00000002.xxxxxxxx
  • 00000003.xxxxxxxx
  • 00000004.xxxxxxxx

Note - If you have a 00000006.xxxxxxxx then that is only for use by the Triggers service, which is an optional install. All other files starting with higher numbers should all be user-created.

On MSMQ 2.0 (Windows 2000), the queues are displayed in the MMC (see picture below).
On MSMQ 3.0 and above (Windows XP and newer), the queues are NOT displayed in the MMC.

 

If any of these queues are deleted, MSMQ will fail to start and throw the corresponding error in Event Viewer.  

Event ID: 2063
Event Type: Warning
Description: Unable to successfully complete initialization of the Queue Manager. Message Queuing may function in an unpredictable fashion.

Event ID: 2020
Event Type: Error
Description: Unable to initialize the administration queue.  

Event ID: 2051
Event Type: Error
Description: Unable to initialize the notification queue.

Event ID: 2052
Event Type: Error
Description: Unable to initialize the ordering queue.  

The easiest workaround is to copy the missing file from another same-version MSMQ machine. The Message Queuing service should then start happily. If there are no other machines handy then you could follow the steps in the KB article. Or, alternatively, dig out your MQBKUP backup.

Other reference material:

174307 Interpreting file names in the Storage directory in Microsoft Message Queue Server and in Microsoft Message Queuing

[[Thanks to Mandi Anez]]