MSMQ Queue Not Processing

I have an rather unpleasant error with MSMQ, one that following the information available on-line isn't fixing. It's resulting in emails (.EML files) going into C:\inetpub\mailroot\Queue and just sitting there not being sent.

Environment Information:
The server in question is Windows Server 2012 R2. My Active Directory domain controllers are 2012 R2 and domain and forest levels are at 2012 R2. I recently upgraded from Exchange 2010, by creating a 2012 R2 server and installing Exchange 2013 SP1 on it which was then patched to CU 19 and is functioning normally and accepts relayed mail (tested via telnet) from the server running MSMQ.

The error that shows in the event log is this Source:

    MSMQ
    Event ID: 2164
    "The Message Queuing service will not join the MyDomainName domain. An MSMQ Configuration (msmq) object exists in the new domain with an ID differing from the service ID. Please delete the MSMQ Configuration object in the new domain, restart the Message Queuing service, and log on again." 

The available information I have suggestions two actions.
1. Deleting the msmq from Active Directory for the server in question.
2. Make sure Network Service on that server is had the specific permission of ' Create MSMQ configuration Objects.

I have removed the msmq object via AD on the server running MSMQ and waited for it to replicate around my domain controllers. (and double checked, by confirming it was gone on each DC).

For the next stage I've tried both rebooting and restarting services, both have the same effect. I restart the Messaging Queuing service (doing this also restarts Messaging Queuing Triggers and Net.Msmq Listener Adapter services).

I get two new event log errors for MSMQ.

    MSMQ
    Event ID: 2116
    "Message Queuing was unable to create the msmq (MSMQ Configuration) object in Active Directory Domain Services. Error c00e0025h"

Directly followed with this error…

    MSMQ
    Event ID: 2164
    "The Message Queuing service failed to join the computer's domain 'MyDomainName'. Error 0xc00e0025"

If I restart the services again, I end up back with this error in the event log "The Message Queuing service will not join the MyDomainName domain. An MSMQ Configuration (msmq) object exists in the new domain with an ID differing from the service ID. Please delete the MSMQ Configuration object in the new domain, restart the Message Queuing service, and log on again."

Now… in Active Directory my server has had the msmq recreated against it.

I've gone round in a circle. I have considered reinstalling MSMQ, this requires removing App server functionality and .Net 4.5. This is a production server that runs some RDP and IIS functions and I'm concerned it would wipe out settings and potentially break the software running on the server.

In the short term, I've written a C# program to manually process the email queue to keep things going, but it doesn't resolve the issue. 🙁

Anyone got any thoughts or ideas on what to try or where else to look?