At one time propagation of dns changes was of great concern to dns administrators. Due to changes in the workings of the gtld and cctld server workings, the old rules of thumb have changed. Name server changes at the registrar level are now very quick. In most cases, the change will be visible in a matter of minutes.
The perceived delays are in the hands of the authoritative and caching dns servers.
Changes made to the dns zone data will not be visible until that zone data is loaded. Some shared dns servers are only reloaded on a scheduled basis. And in one particular case, the dns server will not service queries until it has reloaded all zone data. This may take several minutes where there are many zones.
Once the authoritative dns server is answering queries with the new data, it is available to isp dns cache servers. In most cases, the isp cache will not refresh it's dns records until the ttl for the record has expired. In some cases, the isp cache will not honour the given ttl and a further delay is imposed. This is outside the control of the authoritative dns server.
The key to rapid dns propagation are authoritative dns servers that selectively reload immediately in response to changes committed by an administrator, and a reasonably short ttl that requires compliant isp dns caches to refresh regularly. Furthermore, the authoritative dns servers should be able to continue responding to dns queries during a reload.
Jean-Philippe Bouchard: I start with mydomain.com pointing to the main server with a TTL of 1800 seconds (1/2 hour). I then change it to point to the failover server which simply port forwards to the main server. On the main server, I periodically compute the percentage of requests coming from the failover server which gives me the percentage of people for which the DNS change has propagated. I made the DNS change at exactly 16:04 on 06/21/06 and here are the percentage of propagated users: 06/21/06 16:00 0 % 06/21/06 16:05 3 % <-- after 1 minute 06/21/06 16:10 20 % 06/21/06 16:15 37 % 06/21/06 16:20 59 % 06/21/06 16:25 69 % 06/21/06 16:30 76 % 06/21/06 16:35 80 % <-- after 31 minutes 06/21/06 16:40 86 % 06/21/06 16:45 90 % 06/21/06 16:50 91 % 06/21/06 16:55 92 % 06/21/06 17:00 93 % 06/21/06 17:05 94 % 06/21/06 17:10 94 % 06/21/06 17:15 95 % 06/21/06 17:35 95 % 06/21/06 17:40 96 % 06/21/06 17:45 97 % ... 06/22/06 10:40 99 %