Hetzner и eDNS
Оказалось, что немецкий хостер-лоукостер Hetzner в порядке защиты своей инфраструктуры от атак режет, в частности, входящие фрагментированные пакеты UDP, что в современном интернете частично ломает DNS-сервис. Проблема актуальна только тем, кто держит собственные DNS-серверы на физических или виртуальных серверах в Hetzner.
Детально проблема расписана в базе знаний ISC (наш случай - пункт 4. DNS queries/responses using EDNS are allowed, but UDP fragmentation and reassembly is broken), но решение достаточно простое - настроить свой DNS-сервер сообщать другим серверам не посылать требующие фрагментации ответы. Этакий аналог TCP adjust mss, но для DNS через UDP. Более крупные ответы будут доставляться сразу по TCP вместо UDP.
Для сервера BIND достаточно прописать в секции options:
options {
edns-udp-size 1432;
}