[eqvinox]

Installing a DNS server (personal preference: nsd) on a virtual or dedicated rented box seems to fulfill your mandatory conditions. Did you mean to include something like "web interface" or "managed" in the criteria? What exactly is it that you expect of the "provider" here?

[NTroy]

Yeah, currently I run my own DNS server. However, as traffic grows and so does your customer base and server locations, it would be nice to use a dedicated DNS provider, as they'll already have the infrastructure set up to handle a significant capacity of DNS resolutions quickly, as well as servers around the globe to do so efficiently. In addition to the speed, it's usually also less expensive than setting up and maintaining multiple DNS servers of your own around the world.