An approach for providing telephony and other services over a data network is disclosed. A communications system includes a location server that generates a first subset from the set of all addresses relating to a called party. A proxy server obtains a first subset of addresses from the location server and attempts to establish a session with the called party based on the subset of addresses. In response to whether the first subset of addresses results in session establishment, the proxy server may then request a second subset from the location server. Context information provided by the location server with the first subset may be returned to the location server as part of the request for the second subset.