Another blog post from Guatam highlights the need to scale up some MSMQ parameters when there are many clients.
MSMQ 4 & 5 not receiving messages from Large Number of Clients
To improve performance, MSMQ caches user account information to reduce the overhead from checking if the sender of a message has adequate permissions to access a queue.
As with most caches, the size is fixed and old data is purged when there is no room left. Unfortunately, there is a potential situation where the clean-up process fails which prevents new clients from delivering messages.
To get round this blocker, make sure the cache is large enough to accommodate all possible users of the MSMQ system without needed to clean up.
This is done through the HKLM\SOFTWARE\Microsoft\MSMQ\Parameters\UserCacheSize registry value (default is 253; maximum is 4 billion).