Is there a reason not to use the DNS provided free by reliable web hosts (Rackspace, Softlayer, Linode, etc)? Or is everyone in this discussion hosting with Amazon and the like that doesn't provide that?
We found Godaddy's free dns service was causing a noticeable number of random "website not found" errors. While it might have been mitigated by adding a secondary dns provider we decided to find a more robust primary dns solution plus a secondary dns provider.