This document collects the results of the “INTEROP Investigation Team”. It was formed for the first call of the Open Construction Cycle of NEXOF’s Open Architecture Specification Process in the Core Service Framework Area concerned with the topic Interoperability of Message-Based Service Interaction. It gives an overview over message-based interoperability, interoperability models and dimensions. Guided by a proposed taxonomy for message related interoperability it points out various problems of Interoperability.