Finally, trying to debug this I see some problem with TCP connections to the nameserver:
However, TCP connections with the nameserver work fine from my side. So I’m not sure if there is some TCP blocking somewhere or any other problem. I’d appreciate any help with this.
Right. I don’t have access to the nameservers, but I will ask for the ipv6 to be fixed or at least for the AAAA records to be removed until they can fix it.
Well, it turns out that the problem was with DNSSEC in one of the child zones. In particular the child and parent zones were hosted in the same server, which prevented validation. The solution was to eliminate the child zone and move the records into the parent zone.
For the record, letsencrypt doesn’t need the ipv6 addresses working even if they are defined.
It’s really unfortunate that the error messages of letsencrypt are so uninformative and difficult to debug. Thank you @JuergenAuer and @rg305 for helping with this.