Nós finalmente entendemos isso. Quando você instala o MSMQ, há uma opção para integrar ao Active Directory. Isso está ativado por padrão e na minha situação foi necessário.
Ele aparentemente se integra espelhando sua fila no servidor do AD em sua máquina.
Às vezes, quando você exclui uma fila local, ela não replica essa exclusão para o servidor do AD. Quando isso acontece, o erro se produz quando você tenta adicionar novamente a fila.
A correção é fazer com que o administrador do AD navegue até o console de Gerenciamento do Active Directory e, em seguida, clique nos recursos avançados e faça uma pesquisa detalhada no seu computador e remova a Fila em questão. Então você pode adicionar novamente sua fila à sua caixa.