In a Voice Over Internet Protocol (VoIP) system for completing telephone calls over the Internet, the system uses a general routing table and client exception routing tables to instruct originating gateways about how to complete calls. When a call request for a particular client is received, the system first looks to that client's exception routing table to see if routing information for the call is available. If so, the system will use the routing information in the client's exception routing table to complete the call. The routing information in the client's exception routing table could include information about preferred destination gateways and/or preferred Internet Service Providers. If the client's exception routing table does not contain information that could be used to route the call, then the system simply uses the routing information in the general routing table. In some situations, the system could utilize multiple general routing tables. Likewise, a single client could have multiple exception routing tables.