Definitely look at multiple carriers, preferably delivered via methods that have some redundancy (SONET ring, seperate cable entrances to the building, etc.).
Also, a well-designed, built, and maintained VOIP PBX can reduce the single points of failure down to the station cable and the IP phone itself. Mitel has been doing some interesting stuff in this area with PBX resiliency (2 PBX's that share database info, an IP phone can fail over to the 2nd if the primary fails), and I'm sure there's similar setups available from other vendors as well.