With lots of customers developing systems that use MSMQ across WANs, I find that I get a number of calls on problems getting messages through. Usually sending messages works a treat but pulling them back again doesn't. The main reason for this is the tightening up of MSMQ's use of RPC as documented in the Message Queuing security overview. The "Secured remote read" feature will need to be tweaked if you plan to work across forest boundaries - even if you don't, this problem can appear in development where the test machines are in different forests to the production servers. As the article says:

Message Queuing 3.0 cross-forest clients on Windows Server 2003 family computers in non-trusted domains will use the secure remote read interface. By default, the Message Queuing 3.0 server requires domain clients to establish an encrypted channel, and such a channel cannot be established between non-trusted domains. Thus remote read requests from such clients will be rejected. To modify this default behavior and allow the Message Queuing server to accept domain clients that do not establish an encrypted channel, create a DWORD value Security\NewRemoteReadServerAllowNoneSecurityClient in the registry and set it to 1.

No, I don't know why the registry value is so horrendously long.

Also, the article talks about the Security branch - make sure you use HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\MSMQ\Parameters\Security and NOT HKEY_LOCAL_MACHINE\SECURITY.

Update April 11th - This also seems to do the trick if you are using local accounts on machines in domains. That is, if you are logged in as a local admin, or the application/service is running under a local account, then you can't create a secure channel and so remote reads won't work. The workaround is to use domain accounts OR set NewRemoteReadServerAllowNoneSecurityClient=1.