MSMQ and Global Catalogues
This post is part for my own benefit as I can NEVER remember where the tick box is for setting the Global Catalogue.
A machine with MSMQ installed in Active Directory mode expects to be able to talk to a Global Catalogue in the same site as itself. Note this is a SITE requirement and NOT a DOMAIN or FOREST requirement. MSMQ does not follow domain boundaries - it only cares about the AD site it is in.
As you can see from:
there are a few MSMQ objects copied to the GC so make sure that tick box is checked on at least one domain controller per site.