Sim, é possível colocar IPs na lista negra para sondar o DNS. Imagine um cenário em que um usuário abusivo investiga o servidor DNS um milhão de vezes por segundo (apenas um número figurativo). Isso certamente causaria uma tensão. Essas são as razões para a inclusão de IPs na lista negra de inqueries do DNS.
Ironicamente, esse é um cenário de auto-preenchimento. Você faz uma solicitação porque não há entrada no cache. Em seguida, ele nega a solicitação e, portanto, não salva nada na solicitação. Então você repete a situação e acaba fazendo inúmeras solicitações.
Eu (ou nós) não podemos concluir como o MessageLabs teria estruturado sua resolução de DNS. No entanto, se eles configurarem para que sejam o último buscador do UltraDNS para seus registros MX, esse cenário pode realmente ocorrer.
A única resolução é: 1) desclassificar seus IPs por ultradns. ou 2) eles usam um sistema DNS diferente de uma forma ou de outra. ou 3) criar hard links para o dns, anexando IP ao nome do host no arquivo hosts para o remetente.