Servers and services are not the same thing. I always had more than one machine, each in different geographical areas. Shell scripts kept mail stores in sync, and stupid DNS tricks were used to direct users to servers that were alive. The overall costs were low too. I'd convince the ISP I was working for to let me colocate a pair of old desktops, and trade one with a friend I'd never met face to face.

To clarify my other statement, the biggest "issue" i've had is during a failure of the primary MX messages marked as read would sometimes revert back to being unread for a few minutes.