And you cant compare DNSimple / Route53 as suggested on twitter with DNSMadeEasy. Both in features and more importantly SPEED!.
DNSMadeEasy is already one of the best out there. Most of the others that offer similar features and speed are multiple times more expensive.
As far as i know there are only two other alternatives / recommendation. Cloudflare, which is free. Their DNS are quite fast, but i think there are limitation with what you could do with it.
And if you grow larger, EdgeCast recently offers DNS services as well. Although it start at $50, its price on per million queries are one of the cheapest in terms of paid DNS services. And like its CDN network it is very fast.
For comparison, we have a bare-metal E3113@3GHz machine that at the time happens to run only a full-fledged PowerDNS server (sqlite + pipe backends, query cache disabled due to split-horizon requirements, and passes queries to a pdns_recursor if can't answer directly). The server easily handles about 500M reqs/month, with negligibly low load average. Judging from top(1) output — pdns_server-instance has about 2-4% CPU consumption, most of which is probably due to disabled caches.
But there are probably cheaper options with specialized services.