Here's a problem that only affects Windows Vista and MSMQ 4.0, resolved in the recent service pack:

 929787 Message Queuing 4.0 may not send a message to a remote public queue if the dNSHostName attribute on the Active Directory object of the destination computer is not set

Here's a screen-shot to help with checking the attribute with ADSIEdit. I hate text-based step-by-steps as it is so easy to miss something amongst all the text. It would be so much easier if we included graphics too to speed things up and give you a visual reference to check what you are doing against.

If you are not ready to deploy service pack 1 yet then you can:

  1. Correct the dNSHostName to contain a Fully Qualified Domain name (FQDN)
    or
  2. Bypass Active Directory by sending messages with Direct Format Name addresses