Service-Oriented Computing (SOC) has been marked as the technology trend which caters for the interoperability among the components of a distributed system. However, the emergence of various incompatible instantiations of the SOC paradigm e.g. web, grid and p2p services, as well as the interoperability problems encountered within each of these instantiations (e.g. web service interoperability problems addressed by the WS-I Basic Profile) state clearly that interoperability is still elusive. In order to address this problem we first need to identify all problem dimensions and consequently to provide appropriate solutions. Within this paper we describe a set of interoperability dimensions that need to be considered and we present a generic service model which we view as a first step in addressing some of the identified problem dimensions.