Certificate not getting issued due to DNS lookup timeout on A and AAAA records

I think your problem is the same as mine, which I detailed here: DNS timeout from Let's Encrypt servers - #8 by kenh1

(The domain in my posting is not in .mil, but the nameservers for it ARE in .mil). I also tried a lot of testing along the way (even using a collection of RIPE Atlas probes) and I could not reproduce the timeouts that were reported by Let's Encrypt, either on staging or production. I think recently something changed and Let's Encrypt can not resolve anything under the .mil TLD, which ... kind of sucks? I am not sure there is a way forward here without getting some more verbose output from the DNS resolver stack Let's Encrypt is using.