Locating objects with topology-independent identifiers has emerged as a key functionality in data and information centric approaches to networking. Numerous designs have been proposed to address the obvious scalability and efficiency challenges such systems face in Internet-scale deployments. However, dealing with evolvability and deployability concerns in environments encompassing multiple administrative domains has remained a relatively untouched subject. Taking on this challenge, we base our inter-domain rendezvous design on the incentives and policies of networking stakeholders. The design uses a BGP-like routing structure between the enterprise customers and service providers, and an interconnection overlay between the service providers. We use domainlevel simulations to verify that the scalability and efficiency objectives are not compromised.