Internally, MSMQ uses the Windows-provided CryptoAPI to do all of its encryption and hashing. Starting with Windows NT 4.0 Service Pack 2, CryptoAPI had a bug in its implementation of RC2 encryption in the enhanced (128-bit) provider: the keys were generated with an effective length of only 40 bits, not 128. This directly affected the ENHANCED privacy level of MSMQ's encryption feature, especially since those versions of MSMQ used RC2 by default, so most customers were probably using that rather than the unaffected RC4.
This CryptoAPI bug was fixed in Windows 2000 Service Pack 4, Windows XP Service Pack 1, and Windows Server 2003. At the time the fix came out, many MSMQ clients and servers were still running on unfixed version of Windows, presenting a compatibility problem: without some kind of special measures, fixed and unfixed versions of MSMQ would be unable to exchange messages using enhanced RC2 encryption because each side would see the key length generated by the other as incorrect and the decryption would fail.
For MSMQ on Windows 2000 SP4, a pair of registry values were added. One value controlled the effective length of keys used when encrypting messages with enhanced RC2, and the other value controlled whether to accept incoming messages encrypted with enhanced RC2 but having "short" (40-bit) keys. The defaults were to continue using 40-bit keys when encrypting and to accept them on incoming messages, thereby allowing transparent compatibility with MSMQ installations on unfixed machines.
For MSMQ on Windows XP SP1 and Windows Server 2003, a similar pair of registry values were added. On these operating systems, the defaults were to use 128-bit keys when encrypting but to accept 40-bit keys on incoming messages. Thus, these installations can transparently accept messages from unfixed machines but require configuration to send messages to them using enhanced RC2 encryption. These registry values and defaults are also present on Windows Vista and Windows Server 2008 but are less important, because MSMQ4 will always use RC4 when sending to earlier versions of MSMQ unless other registry values have been set to force the use of RC2.
It has been many years now since this CryptoAPI bug was fixed and hopefully all of your MSMQ installations are on fixed versions of the OS. If that's true, what can you do to ensure that MSMQ throughout your enterprise is really using 128-bit keys, thereby tightening up your security? (All of the registry values listed below are created under HKLM\SOFTWARE\Microsoft\MSMQ\Parameters\Security. The MSMQ service must be restarted for these values to take effect.)
One additional thought: before touching anything, search for the SendEnhRC2With40 registry value on Windows XP and above. If it is present with a nonzero value, that means that at one time that machine needed to send messages encrypted with enhanced RC2 to an unfixed machine. Thus, any machines which that one communicates with have an increased chance of still being unfixed and candidates for double-checking.
The original documentation of this issue can be found in item 4.20 of the MSMQ FAQ.