System.Messaging.MessageQueueException (0x80004005): A workgroup installation computer does not support the operation (Public Queue create issue)

This is a weird issue that I don't fully understand why it would happen. But the symptoms are very persistent as we're able to reproduce these behavior easily.

Issue:

The MSMQ (Microsoft Message Queuing) fails to create Public Queues and throws  "the System.Messaging.MessageQueueException (0x80004005): A workgroup installation computer does not support the operation" exception.
Users were not able to create Public Queues for their services and received the above mentioned error. 

Cause:

This happens if you install and remove MSMQ and reinstall it again on the same server.

Solution:
I was able to remediate this issue every time by following these steps;

1. Make sure you have a "Local Administartor" account enabled on the computer and that you have access to that accounts credentials. If not, create a new local account and add this user into the local computers "Administrators" group. We will need this account later.
2. Uninstall MSMQ feature from the server and reboot.
3. Remove the computer from the Active Directory by joining the computer into a workgroup. Restart!
4. Remove the computer account from active directory. You should be also asked to remove the subtree of the computer's AD object. Accept and remove the computer account.
5. Login into the server with your local administrator account and join the computer back into the domain. If you are in a big environment with lots of DCs on your domain, you're better off creating the computer account manually in the domain and joining the computer.
   Once the computer is joined in the domain, reboot.
6. Install the MSMQ again and start the process/service responsible of creating the public queues.

References;

There are a lot of useful sites out there. But for me, here are the some methods I learned during the troubleshooting of this issue.

Start with available PowerShell commands;

Clear-MsmqOutgoingQueue

Clear-MsmqQueue

Enable-MsmqCertificate

Get-MsmqCertificate

Get-MsmqOutgoingQueue

Get-MsmqQueue

Get-MsmqQueueACL

Get-MsmqQueueManager

Get-MsmqQueueManagerACL

Move-MsmqMessage

New-MsmqMessage

New-MsmqQueue

Receive-MsmqQueue

Remove-MsmqCertificate

Remove-MsmqQueue

Resume-MsmqOutgoingQueue

Send-MsmqQueue
Set-MsmqQueue
Set-MsmqQueueACL

Set-MsmqQueueManager
Set-MsmqQueueManagerACL

Suspend-MsmqOutgoingQueue

Some useful links;

MSMQ Offcial Microsoft Support Page
https://docs.microsoft.com/en-us/previous-versions/windows/desktop/legacy/ms711472(v%3Dvs.85)

Overview of Message Queuing Services Architecture

https://docs.microsoft.com/en-us/windows/win32/rpc/overview-of-message-queuing-services-architecture

What publically available tools are there for troubleshooting MSMQ problems?

https://blogs.msdn.microsoft.com/johnbreakwell/2007/12/13/what-publically-available-tools-are-there-for-troubleshooting-msmq-problems/

MSMQ Transport Troubleshooting

https://docs.particular.net/transports/msmq/troubleshooting

Diagnosing MSMQ Problems
http://resources.arcfmsolution.com/10.1/ResponderConfig/TS_MSMQ_DiagnoseMSMQProblems.html

Troubleshooting Queued Messaging
https://docs.microsoft.com/en-us/dotnet/framework/wcf/feature-details/troubleshooting-queued-messaging