Why aren't our DNS records propagating out into the internet?
Yes, you are misunderstanding how DNS works. I'm going to use some emphasis here, but please don't be offended as none is intended.
DNS RECORDS ARE NOT PROPAGATED. THEY ARE CACHED.
That being said, here's a simplified explanation of what happens:
You create a new DNS record (A, CNAME, etc)
A remote user (more specifically a process\application launched by the user) tries to access a service accessed via that DNS record (a web browser trying to access the web site running on funny.example.com for instance)
The users DNS client sends a DNS query to it's DNS server, the DNS server then finds your name servers (usually through a series of recursive DNS queries) and asks them for the information regarding funny.example.com
Your name servers respond with the answers
The users DNS server then sends this information to the user (more specifically to the users DNS client resolver), which in turn returns the information to the process\application. This information comes with what is called a TTL (Time To Live) that tells the DNS client resolver how long this information may be kept in it's DNS cache (in memory) and how long the information can be considered current and accurate
The user's DNS client resolver then flushes this information when the TTL expires. Any new requests for the DNS record(s) in question requires a new DNS lookup and the above process repeats.
So the long and short of it is this:
Your DNS records do not propagate. No other DNS server has a copy of your DNS records or zones. A DNS client or server may cache information about your DNS records or zones (based on their DNS queries of your DNS records and zones) into their DNS cache. This information is temporarily cached and will be removed from their DNS cache when the TTL expires.
If your name servers are down, only those DNS clients that have any of your DNS records in their cache will be able to resolve those DNS records and only until the TTL expires. Also, when the TTL expires (neccessitating a new DNS lokkup) those DNS clients will no longer be able to resolve your DNS records.
it would help a great deal if you told us your actual domain name, then we could answer your question with reference to your actual setup, and point out any faults.
I tend to trust http://dns.squish.net/ for diagnosing DNS problems quickly. That will tell you for certain where your issues lie after you've made a change - basically if your delegation from upstream is correct, and your 2-3 name servers all give the same answer, and someone isn't seeing the new record, they will just have to wait for their local network to see the changes. If that checker tells you one of your servers isn't giving the same response as the others, you need to fix that problem.
There's no way you can publish DNS changes instantly - well, you can publish them instantly, but the rest of the world will lag behind according to the TTL setting of each record, so e.g. if you've set a TTL record of 86400 seconds (one day) and you make a change, others will see the old record for up to a whole day, because their local cache won't ask you until their copy of the record expires.
I would suggest that before any major DNS changes you reduce your TTL to 600 (10 minutes) to encourage caches around the internet not to hold on to old records for very long. But some caches will ignore this, or assume 1 day, or even 1 week.
A rambling answer to a rambling question, hope there was something useful in it though.
Yes the old adage, "DNS changes may take 24-48 hours to propagate through the internet" would be more accurately "DNS changes may be cached on any DNS servers that have queried this record within the past 86400 seconds."
If you want to ensure redundancy of your DNS in the event your server goes offline, you should look into backup DNS service (like at dyndns.com) or create your own secondary NS.
All DNS servers on the Internet are "3rd party-controlled" (I suppose you could consider the root DNS servers to be somehow "proprietary" to the Internet, but there's no technical reason why could put up your own private root, either).
Your DNS server provides a suggested "time to live" (TTL) in each answer it provides. Remote resolvers (other DNS servers performing recursive resolution for clients, client resolver libraries, etc) are supposed to cache the answer for up to that TTL before discarding it from their cache.
If you're not seeing changes that you're making to existing records being reflected in real-world queries it probably means that your TTL values are high enough that you're not waiting long enough to see the existing answers age out of the resolver caches around the 'net.
Some background from Server Fault: Why is it called DNS "Propagation"?
When someone (or some computer) out there on the Internet, so to speak, want to connect to one of your machines, they ask their local nameserver for an IP address matching the hostname they're interested in.
So if you tell someone "hey, take a look at my cool website http://www.example.com", the other guy's computer will ask its local nameserver "hey, what's an IP address for www.example.com?"
Assuming the local nameserver has never looked up the answer to that question before, it will ask the root nameservers to find out which server(s) handle lookups for ".com". When it gets that answer, it will ask those servers which servers handle lookups for "example.com". When it gets that answer, if will ask those servers for an IP address for "www.example.com".
When the server(s) for example.com respond with an IP address for www.example.com, they will also give the requesting nameserver a hint about how long it should remember the answer to this question. That hint is called the "TTL", or "time to live", and it is measured in seconds. There is no guarantee that any server will pay any attention to the TTL - some nameservers may be configured to never remember the answers to lookups, and will always repeat the process even if asked several times per second. Other nameservers may be configured to keep the answer for a long time, even if you have suggested that the data only be kept for a short time, perhaps because they want to minimize network traffic. The TTL is just a suggestion, not a requirement or a guarantee.
The literal answer to your question - why aren't your DNS records propagating out onto the internet - is that they aren't doing that because they're not supposed to.
Also, if you are looking at your own DNS information using a site that's designed to research or debug DNS information, chances are that site isn't going to cache data for long, or at all, regardless of what your TTL suggestion is, because the site's goal is probably to provide information about what the DNS system says RIGHT NOW, not 5 or 50 or 500 seconds ago. This is why your changes are reflected immediately, and why the service stops working as soon as you disconnect your nameservers.
I suspect your underlying question might be "how can I set things up so that if my DNS server reboots or its hard disk dies, other people on the internet will still be able to see my webpages?"
The answer to that question is to set up several nameservers for your domain, and to have them running on different machines - ideally, not just different physical computers, but with different network connections, perhaps even in different cities or states or countries or continents. Most of these nameservers will be set up as "slaves", which means they look to a "master" nameserver for their information, and then repeat that information to anyone who asks them for data.
So, in your WHOIS data with your domain name registrar, you might configure four nameservers for your domain:
ns1.example.com ns2.example.com ns1.otherguy.com ns2.otherguy.com
where ns1.example.com is your current DNS server. ns2.example.com might be another machine in your company/organization - ideally not on the same subnet and in the same server rack (or under the same guy's desk) as ns1.example.com.
ns1.example.com will be considered the "master" server, and when you want to change your DNS, you will make your changes on that machine.
ns2.example.com will be configued as a "slave" server, that just copies whatever data you've set up on ns1.example.com - but the outside world doesn't care about the master/slave distinction, ns2.example.com will be considered just as "official" as ns1.example.com.
ns1.otherguy.com and ns2.otherguy.com are machines that are set up somewhere else - maybe you make an arrangement with a friend/colleague at another organization to run nameservers for each other, or maybe you get set up with dyndns.com or everydns.net or any of the other free or commercial DNS providers. However you work that out, you get those machines configured as slaves, so that they pull the DNS information for example.com from ns1.example.com (your "master"), and they will serve that DNS information to any machine on the internet that asks for it.
Once your domain registrar publishes the new NS records for your domain (which should be approximately instantaneously), then when someone out on the internet asks which domain name server handles "example.com", they'll get four answers -
ns1.example.com, ns2.example.com, ns1.otherguy.com, ns2.otherguy.com
Depending on how the other guy's nameserver is set up, it might treat those four as a list and ask them one at a time how to reach "www.example.com" - or it might ask all four of them the same question at the same time, and just take the answer from whichever machine answers first. Either way, if ns1.example.com is down because the hard disk died or you decided to reboot or whatever, then the other 3 machines will be available to answer the question instead, and your website will continue to be visible.
The easiest way to solve this problem is to sign up with a DNS service provider who will handle DNS for your domain - the price for this ranges from free to thousands (probably even tens or hundreds of thousands) of dollars per month, depending on the level of service you want. You can get reasonably reliable service for $30/yr or so. The free services aren't awful and, hence, have a pretty good bang-for-the-buck ratio, but if you depend on your website to make money, you oughta be able to come up with $30 for a year's worth of DNS.
Then, follow the instructions from the DNS service provider to change the NS records at your domain name registrar, and you'll be all set.