This paper describes the design and the prototype implementation of a programming middleware for coordinating services distributed over dynamic and heterogeneous networks without a public addressing schema (i.e. service addresses are not always public available). We illustrate the problems posed by relaxing the public addressing schema in the context of service orchestration. We discuss the design choices of our middleware. Then, we discuss the actual network technologies underlying the prototype implementation and the formal foundations that drive our approach.