A method for re-querying for routing information is disclosed. The method transmits an initial admission query to a gatekeeper or a request for routing information and receives an admission confirmation or routing information response with a destination address. The method then tries to establish a connection with the destination address. Upon reception of a call failure message including a failure cause, the method, optionally, increments a counter and transmits a re-query to the gatekeeper or other routing entity, and the re-query includes the failure cause and, optionally, a value of the query counter.