I don't generally approve of RRDNS as a mechanism of increasing fault tolerance. If you really want a great network, then you've gotta start with solid building blocks to begin with..
Do your servers have a diverse route to the internet? Do they have independent power supplies? If you're talking about true fault-tolerance, then you need to start a lot lower down the chain.
- Dual (multiple) disks in a RAID layout that isn't RAID 0.
- Dual power supplies, provided by dual redundant diverse power feeds.
- Dual NICs to separate switches
- Dual Firewall/Routers
- Dual (or multiple) Internet transit/peering providers, providing routes to the internet via BGP
Then you can start considering multiple datacentres, which is a completely separate kettle of fish. I'm not entirely adverse to RRDNS as a solution to increase redundancy and resilience, but the initial stuff has to come first.
You'll still have the bigger problems, associated with ISPs rewriting short DNS TTLs, which are required for fast-ish failover to a different DNS provider. I spent a good few weeks doing research about the best way to ensure a system's uptime using a combination of network-layer resilience, using BGP, as well as multiple A records in DNS, and RRDNS. In the end, we decided that Dynect were the best DNS provider for our needs, but YMMV, as always.
It's always worth looking a bit deeper than merely the IP address of your server, to ensure that hardware failures can be endured by a combination of RAID, or multiple servers behind a load balancer, and then you can start really looking at scalability/redundancy. If you've only got one server, with one disk, and one nic, and one switch, then it's all a bit pointless looking past that. Just upgrading everything to be a pair will bring some peace of mind.
As a systems engineer, I now can't count any lower than 2.