One of the main features of 5G networks is the coordinated orchestration of both information technology (IT) and connectivity resources. This enables the deployment of a flexible and programmable architecture able to provision end-to-end services with different (and sometimes quite) stringent quality of service (QoS) constraints. In this paradigm, service orchestration may take place over single or multiple administrative domains. The 5G Exchange (5GEx) project, building on the software-defined network and the network function virtualization (NFV) concepts, targets the design and the implementation of a multi-domain orchestrator (MdO) prototype for the automatic provisioning of network service across multiple administrative domains. This paper presents an architectural solution, designed and implemented in the context of the 5GEx MdO prototype, that can be used to establish end-to-end connectivity tunnels with QoS constraints (i.e., bandwidth and/or end-to-end delay) connecting virtualized network functions deployed in remote data centers controlled by different providers by means of an innovative stateful backward recursive path-computation-element based computation procedure. The proposed solution has been experimentally validated in terms of scalability, reliability, and end-to-end workflow proof-of-concept. Results show how the designed solution permits the automatic establishment of QoS-based end-to-end tunnels spanning across multi-technology and multi-operator network domains. The orchestration scheme does not present scalability issues for either the advertisement of resources or for the provisioning of connectivity services. Moreover, no issues have been identified from the reliability point of view.