I've personally used
www.ZoneEdit.com for over 2 years now and swear by them. I've found their customer support to be excellent, if you have a question about anything, simply call or e-mail them and they'll walk you through it. But their user interface makes that unnecessary for most basic tasks, it's straightforward and intuitive to use. However, more complex things can be accomplished when you have your own control over the DNS records, such as round robin or dynamic load balancing as well as fail-safe fallthrough to a backup server (which means if you have two boxes on seperate hosts with rsync daemon mirroring, you'd never see more than a few minutes down time!).
Their pricing may seem a bit confusing at first, since it's based on credits, which are used as needed. But if all you had were five domains that you wanted to simply provide basic DNS records for, the service would basically be free! With just that, you can switch web hosts at anytime within 3-15 minutes time. Do like I did, try five domains for awhile on their service and I'll bet you'll soon buy additional credits and consider them a bargain for the power and control they give you.
Just keep in mind that the whole 3 day propagation delay is not from changing web hosts, it's caused when you change DNS servers. If you've allowed your web server to be tied to your host's DNS server, you're going to end up losing money unnecesarily.