It’s essential that the challenge record be visible at all of the nameservers for a zone before proceeding. I have an example of how to do this programmatically here, part of a larger example of using nsupdate.
Although come to think of it, even that may not be an adequate guarantee if we’re talking about anycasted DNS. Hmm…