Rackspace offers DNS with all cloud accounts and doesn't charge for it. As far as I know, you can sign up for a cloud account and not actually purchase any services, though I would probably put some files in Cloud Files so you're at least paying them something to keep the account around. You can update your records via their API or via their control panel and there are no per-change or per-domain fees.
You're getting professionally-run DNS servers, distributed with anycast.
Route 53 is also really cheap if you're an AWS kind of guy/gal for 50 cents a domain. The usage charges are beyond low (think 1 cent) for smaller sites.
You're getting professionally-run DNS servers, distributed with anycast.