Thanks for your elaborate answer, @hlandau. It helped me track down some issues with the DNS servers.
I’m sorry to trouble you with some of the quirks of our non-standard system. To answer your last question, the server is not doing “recursion” in the typical DNS sense. We have a few legacy applications that think they run the authoritative nameservers and we need to have a custom actually authoritative nameserver in front of them merging the results with proper fallbacks. It’s a temporary solution and it’s so ugly I don’t want to explain it further - everything is possible in legacy maintenance.
What’s on-topic for Let’s Encrypt which would probably save us from all the troubleshooting problems is better error message. It looks like the ACME server (boulder) consistently reports the error as if it happened while checking “_TXT for acme-challenge.kkv.pl”, while in fact it really is checking “CAA for kkv.pl”. I would consider this as a bug as the error message is misleading.
I have updated the bug report with the new information but somebody closed it already.