MSMQ Firewall Ports
I eventually found this article: How To Configure a Firewall for MSMQ Access . And this article: Clear the way - MSMQ coming through
To recap, you need ports 135, 2103 and 2105 open in order to read a message from a public queue.