Have you verified that all nameservers for that zone deliver the TXT records before telling Let's Encrypt to verify the challenges?
Yes. Our tool here first checks if all our DNS have acme records propagated correctly and only then sends request to letsencrypt.
The ACME server (boulder) has 1 minute DNS cache, if my recollection is correct.
I believe it's 1 minute or the value of the TTL on the record, whichever is lower.