We've been using dnsmadeeasy[1] for years. There's something dated about their interface/presentation, but the service has been rock solid and fast since day one.
Edit: Not that it matters much, but it was Textdrive's (née Joyant) recommendation back in '04 that got me to sign up. If anything, they've been around a while.
https://web.archive.org/web/20060427025139/http://forum.text...