Obrigado pela ajuda aking1012, e obrigado parallels fóruns: link
Este foi realmente um problema de DNS. Nosso servidor de nomes tinha uma entrada curinga ('*') que resolveu nosso domínio. Quando fiz ping em um domínio inexistente em qualquer um de nossos servidores, ele estava sendo resolvido para nosso domínio novamente. Eu peguei a entrada curinga no registro da zona DNS e bingo! No encadeamento mencionado acima, há idéias sobre o que pode ser feito sem ter que remover a entrada curinga. No nosso caso, fazia sentido retirá-lo.