It might be a firewall (or router, or other network device maybe even before getting to your ISP) that blocks traffic selectively. In order for Let's Encrypt to be sure that you control the name as seen from everywhere on the Internet, they need to check from multiple places on the Internet.
Well, are the responses that your authoritative DNS server gives to requests from around the world the correct IP, which is routed to the server that you're trying to use?