Novel Internet applications demand global availability of complex services that can adapt dynamically to application requirements. At the same time, pervasive Internet usage and heterogeneous access technologies impose new challenges for service deployment. We present Spontaneous Virtual Networks (SpoVNet), a methodology that enables easy development of new services with transparent support for mobility, multi-homing, and heterogeneous environments. This article presents the overlay-based architecture of SpoVNet that supports the spontaneous deployment of new services as well as a seamless transition towards future networks. SpoVNet´s architecture offers support for the underlay aware adaptation of overlays by the use of cross-layer information. In the context of two exemplary services like a group communication service and an event service as well as two demanding applications – a realtime online game and a video streaming application – we illustrate how SpoVNet is of value in establishing services and applications for the Next Generation Internet.