We recently wrote a tool which can populate our DNS entries in either Route 53 or another provider (can't recall which). So if one goes down, we can run a script which brings up our DNS entires in the alternate provider.
I guess someone could service-fy this and have a meta-DNS service which let you switch backend providers.
Make it so.