Recomendation for DNS host?

So I have to leave my DNS host as we are going to be dropping their access and I think Their rates for DNS hosting without service are insane:

http://www.illinois.gov/icn/services/institutions/Pages/dnshosting.aspx

Perhaps they aren't? I've never seen a bill before. I've heard about cloud DNS but I'm looking for recommendations. Our Registrar is Network Solutions and I've quickly looked over their page once or twice but i didn't see DNS hosting only.

Those are enterprise business rates.

If you are not an enterprise business and are only a home user, you can use any managed DNS provider:

http://en.wikipedia.org/wiki/List_of_managed_DNS_providers

My suggestion personally is http://dyn.com/standard-dns/

If you have enterprise level queries (think 100K hits per day), you'll be paying the higher rates.

EDIT:
If Illinois has your domain name, you're SOL.. If you are under contract with the state to have a certain .il.us name or something like that, you're probably screwed. If you have a .com or .org or even a .edu, you're probably able to change it to what you want. Reverse DNS, however, may bite you in the ass. Depends on how giant of a bag of dicks the ICN is.

Yes I'm looking for business level DNS hosting, we are ending our contract with ICN, hence the reason why their non-access rates don't seem favorable.

We own own our domain and it's a .org

I know I can find a list of DNS hosts, but I'm looking for recommendations so I can avoid hidden gotchas.

I used Hurricane Electric for years with no issues...

Recently I migrated most of my DNS to namecheap when I transferred my domains to them.

However, I have four sites I'm hosting my DNS thru CloudFlare with... and it is fucking amazing: http://www.cloudflare.com/

Is this just for web and email or something more complex? Many registrars offer free DNS. eNom is one, and I've used them for years for many domains without issue. Certainly something worth looking into if you're not married to Network Solutions. I register everything on eNom through namecheap, which has a pretty good control panel for making DNS changes and additions. IIRC, the TTL they set on resource records is just 5 minutes, so changes propagate quickly.

I've used ZoneEdit for years... and they now have free accounts again under the new ownership. Though I've had a grandfathered-in free account the whole time.

The only thing that would get me to even CONSIDER anyone else is if they shut down.

I second dns.he.net

Been using it for years without any downtime.

Gandi.net are really good and have lots of large organizations.
//Danne

Thanks for the leads and certainly the info about zone edit. I went looking for them for personal service and when I saw new owners, I thought I better research them again.

Right now we just have a few web servers and exchange, however this may change and I believe I read something about a special record needed for Google integration for syncing your domain.

one of the better out there

http://dyn.com/dns/