The paper presents some challenges to Seamless e- Government, and proposes a technical solution ? Government-Enterprise Ecosystem Gateway (G-EEG) to address them. G-EEG is a framework through which multi-organizational processes and applications can dynamically build, apply and evolve complex communication structures to asynchronously exchange messages in specific application contexts, e.g. to deliver seamless public services. In addition to basic messaging, G-EEG supports high-level messaging functions through dynamically-enabled horizontal (process-independent) or vertical (process-dependent) extensions. A number of extensions are described as solutions to the challenges for seamless e-Government. Currently a research prototype, G-EEG is specified formally and implemented using open standards.