I have a similar situation, in my case if BizTalk tries to send a message to PRPS_REQUEST.CATALOG.QR, it works. If it tries to send a message to PRPS_REQUEST.CIDS.QR it fails with Reason Code = 2354.
Both use the same transmission queue to pass the request to the remote system. The different remote queues are to set different remote queues in the xmit header.
I could understand if it was happening to both, but it only happens to the second remote queue.