A major goal of service-oriented architectures is to enable software interoperability in heterogeneous and dynamic environments. Web services standards and protocols aim to support this goal and middleware systems implementing these standards and protocols consequently are needed. Maintenance and administration of middleware is made difficult due to variations in standards and their constant evolution. In this paper, we introduce a new service-oriented middleware architecture for runtime Web services interoperability. Different from other middleware systems our approach applies service-oriented computing principles on the middleware layer, thereby establishing an on-demand model for middleware features. Clients can use middleware as services, dynamically discovering and using the services as interoperability requirements are determined. Further, middleware as services allows middleware to be provided and managed separately from its clients. We present the policy-based programming model, architecture, and details of our middleware, and discuss new challenges that arise in this context, such as distribution of middleware services. The approach is validated through a scenario integrating web service transaction middleware.