Ask HN: DNS host suddenly deleted us - fastest way to get your DNS back?

We had a terrible incident on Saturday where an engineer at our hosting provider deemed it relevant to remove our managed DNS service along with unrelated server removal we had requested, with no indication that they would do this. Fortunately I was able to change our name servers quickly, but it left some customers without service even until now, as some DNS caches haven't refreshed. We have server backups, load balancers, text alerts, server monitoring - everything we can do within our small budget to keep online 24/7. We never anticipated we might lose DNS. We're going to add more NS entries to another provider, but is there anything further we can do? Would love to hear any stories. It was a crazy weekend I don't want to repeat.