Novel Internet applications demand for global availability of complex services like group communication and QoS support. At the same time, pervasive Internet usage and heterogeneous access technologies impose new challenges for service deployment by increasing mobility, multi-homing and heterogeneity. In this paper we present Spontaneous Virtual Networks (SpoVNet), a methodology that as main objectives enables i)~easy development of new services with transparent support for mobility, multi-homing, and heterogeneous environments, ii)~a seamless transition towards the Future Internet. The contribution of this paper is threefold: First, it presents the SpoVNet architecture and illustrates how the architecture can achieve objective i) and ii) using an overlay-based architecture. Second, the paper shows how by consistent use of crosslayer information and modelling the SpoVNet overlays can be optimized and adapted to network dynamics. Third, it illustrates the effectiveness and applicability of the SpoVNet architecture by using two exemplary services - a group communication service and an event services - and two demanding applications: a realtime online game and a video streaming application.