If you try to send authenticated messages between machines in different forests, you will see them end up in the Transactional Dead Letter Queue (assuming you enabled source journaling). This is because authentication uses certificates that are stored in Active Directory but forests - even those with two-way trusts - cannot share this information. So when a message arrives at a destination, the recipient tries to use the certificate to look the corresponding user account up in its local Directory Services but is unable to find a match. MSMQ then sends a negative acknowledgement back to the sender saying "signature invalid".

As discussed below, the solution is to use external certificates generated by a CA.

Message Authentication
“Message authentication provides two services. It provides a way to ensure message integrity and a way to verify who sent the message. To request authentication, the sending application must set the authentication level of the message to be authenticated. When authentication is requested, a digital signature and a user certificate are attached to the message in addition to the sender's SID, which is attached to all messages in the sender identifier property (PROPID_M_SENDERID or MSMQMessage.SenderId) by default. An internal certificate generated by Message Queuing or an external certificate supplied by a certification authority can be used. By default, Message Queuing attaches the internal certificate for the user to the message. An external certificate can be attached directly by the sending application, or an internal or external certificate can be attached by Message Queuing at the request of the sending application using a security context structure specified in the message.”

This does require some extra coding to make use of the external certificate as MSMQ looks after internal certificates for you.