Eu finalmente encontrei este artigo: Como configurar um firewall para acesso ao MSMQ . E este artigo: Limpar o caminho - MSMQ vindo através de
Para recapitular, você precisa das portas 135, 2103 e 2105 abertas para ler uma mensagem de uma fila pública.