Normally licensing questions are very few and far between which is why I don't think I've posted about the subject before. On the MSMQ newsgroups, someone posted that they had:

"observed that the number of users capable of connecting to such queue depends on the number of concurrent connections set in the Licensing mode Windows 2003 Server."

This is correct. If you are using the native MSMQ protocol to send messages, or RPC to receive them, then you need a Client Access License (CAL). This requirement is documented here:

INFO: CAL and Connection Usage by MSMQ

"MSMQ checks Windows NT CALs only for message transfer sessions.
A CAL is not required for other forms of MSMQ network traffic, such as creating, locating, and deleting queues."

Note that the KB article is a trifle old and some references no longer apply, such as the need for SQL licenses (MSMQ 1.0 only).

It can become a problem to determine the optimum number of CALs required because of the length of time that a network connections between MSMQ machines can be in use for. Other applications may only make contact for a short period, allowing for many users to perform work at roughly the same time without exhausting the licenses. As a result, for example, 100 people may be able to use a server configured with 30 licences. MSMQ connections, though, last from minutes to months and the re-use of licenses is much less efficient. In large companies, this need for licenses may become expensive.

So what are the alternatives?

One that does not require a major redesign is to send MSMQ messages over HTTP. As the messages are POSTed to a web application, the licensing model is different although not as simple. It is important to take into account how the clients are authenticated and where they are located.

Looking at the Windows Server 2008 Licensing FAQ

Q.  When do I need to acquire a Windows Server 2008 CAL? 

A.  A Windows Server 2008 CAL is required when a user or device accesses or uses the Windows Server 2008 server software. However, if access is through the Internet and is anonymous (for example, when browsing a public Web site), a Windows Server CAL is not required. Also, if that user is an external user, another option is to acquire an External Connector license.

So if clients are sending MSMQ messages over the Internet without being authenticated then no CAL is required. If the clients are to be identified, though, then you could go for the External Connector license option.

An alternative, although still using HTTP support for MSMQ, is to deploy Windows Web Server 2008 as the same FAQ says:

Q.  Do I need to acquire Windows CALs to access servers running Windows Web Server 2008? 

A.  No. Windows CALs are not applicable to Windows Web Server 2008. However, Windows Web Server 2008 can be used as the scale-out front end for applications such as Windows SharePoint Services. In these scale-out configurations, Windows CALs will be required since servers running Windows Web Server 2008 are connecting to back-end applications running on Windows Server 2008 Standard and above.

As MSMQ comes with Windows Web Server 2008, I don't expect it to be treated in the same way Windows SharePoint Services are in the answer above.

I'll revisit this post if I come across some different approaches, such as concentrating connections with store-and-forward servers.