We use DNSMadeEasy and it is very smooth. Reasonably priced and they have not had any downtime in 2 years. We also use they for our SMTP mail as well which makes things easy.
For some reason, I'm a bit of a DNS geek, and have followed this area for years.
DNS hosting is basically a solved problem, i.e. it is not that hard to build a good DNS infrastructure and get perfectly good speed and reliability. There are quite many good providers out there.
In addition to the good answers already given, I'd like to mention Gandi. Their DNS servers are not Anycast'ed (i.e. no multisite with the same IP addresses BGP routed for failover and speed), but they have been perfectly reliable and responsive for me for years. They have 4 things that I like:
In addition to Gandi, I would suggest DNSMadeEasy & DynDNS & EasyDNS as other good recommendable providers (no particular order, their services and prices differ a bit, take a look around).
If reliability is a major decision point, maybe I'd say DNSMadeEasy looks a bit better than Gandi, and DynDNS Dynect seems best of them all. But note, that's just based on their implementation and past performance, I cannot make any promises for future performance.
I've used several DNS hosts, including ones mentioned on this list. The one I like best is Nettica (http://nettica.com ). Great interface and great pricing.
DynDns has a good paid offering with a SLA: http://www.dyndns.com/services/pricing/#dns. At $300/year it does not seem very expensive, and does offer a SLA, so it's better than self-hosted.
My knowledge about this is limited though, there might be other hosts out there who can beat this deal.
You could ask in http://ServerFault.com, they for sure can give you more options. Outsourced DNS services is not something us normal folk use very often, so you will probably have better luck in ServerFault.
I have used DNSmadeEasy for hosting DNS for some productions systems we ran. It has that nice failover feature and customizability. Price is right too.
https://entrydns.net/ is a free DNS service I built in my spare time together with a sysadmin friend.
We hope to support it via donations and/or unobtrusive affiliate sales, and add more features in the future. Give it a try.