Discovering networked services in pervasive computing environments is problematic as multiple Service Discovery Protocols (SDPs), differing on their services description formats as well as advertisement and request models, have already become (de-facto) standards. This calls for a solution to SDP interoperability, enabling clients to locate networked services independent of the SDP they use to advertise their presence. In this paper, we report on our experience in developing two such solutions: the transparent approach of INDISS based on message translation, and the explicit approach of MSDA based on protocol integration. While efficient and able to support legacy clients and services, INDISS is limited by the basic service information available in existing SDPs, and assumptions about the network protocols used by the SDPs. Advanced discovery features required by pervasive environments, such as context or security management, can only be provided by more complex discovery frameworks like MSDA, but come at a price.