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.
Came here to say the same. DNSMadeEasy doesn't feel _fancy_, but it has always worked great for us. Solid service. Highly recommended.
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.
[1] http://www.dnsmadeeasy.com