I just read about Amazon's new Route 53 scalable DNS service in the cloud. It seems like an affordable way of upping the reliability of a few high-volume zones. But at a cost of $1/month per zone, it is not price-effective if you want to manage several hundred low-volume zones.
Just because a zone has a low volume of requests, doesn't mean it should not be reliable. I'm looking for a scalable DNS web service that can be managed via an API that is affordable for managing many low-volume zones.
Or should I just run a DNS server on a cloud Linux box?
I know this is abit late but we use Rackspace Cloud DNS, not had any issues yet. http://www.rackspace.com/cloud/cloud_hosting_products/dns/
How about Zerigo they even have a free tier. https://www.zerigo.com/managed-dns/pricing
I believe Dyn.com does this, take a look at e.g. http://dyn.com/open-dialogue/dynamic-discourse/dynect-api2-preview - haven't looked at it myself in detail though...
I am using CodebaseHQ for my SVN and saw a while back that they offer DNS with API called PointHQ
Rolling your names servers might be way to go, if your requirements are not too complicated, you could just write software that creates the config files for Bind.
Since you are planning on having quite many domains, another option might be a reseller account at Joker.com. Joker provides free of charge basic DNS services for domains that are registered through them and for resellers there is also API.