I have a customer set up with www.dyndns.org Backup MX and Backup DNS services. So far I'm pretty happy with the result. They'll store mail destined to your server for up to a week if your mail server cannot be contacted. Spam filtered too.
Could you provide more details? For instance, how was your failover server configured?
In terms of dns you could probably run a slave server for someone else in exchange for them running a slave server for you. This type of exchange is actually fairly common.
As far as backup email, depending on the amount of mail you push you could consider going active/active and running two mail servers, each in a separate facility; one would pick up the slack if the other went down, so you get redundancy, and when they're both up you can handle more traffic. Or you could simply try to get your failover scheme working correctly . . . Both can be pretty robust solutions, depending on the quality of the network you're on and your budget.