I guess in the last 3 years this is a bit of a solved problem. Here are some to check out:
- Amazon has a nice dns service now http://aws.amazon.com/route53/
- Linode has a free api based dns if you’re a customer.
- Dynadot has a fee dns with an api if you’re a customer.