You could query your authoritative name server(s) first and only query other resolvers once you see your new record. Shouldn't be to hard to automated that using something like dnspython.
If the authoritative is using Anycast (which they should) then you run into similar problems that you get with Anycast resolvers, which is to say you might get different results depending on distribution of data. Due to this we currently provide an API for checking distribution of zone changes with our authoritative name servers: (https://developer.dnsimple.com/v2/zones/#checkZoneDistributi...).
