Isso parece uma incompatibilidade nos tempos limite da tabela de estado NAT do firewall e nos próprios tempos limite do servidor DNS.
A Porta ICMP Inacessível está sendo retornada pelo seu servidor DNS, provavelmente em resposta a um pacote recebido atrasado. BIND escolhe uma porta aleatória (ish) para cada consulta de saída e é possível que uma resposta demorada chegue muito depois que o BIND parou de escutar a resposta nessa porta.
Isso faz a pergunta de por que o firewall felizmente permite que o pacote retorne (atrasado), sem subsequentemente deixar o erro ICMP de volta.