Directory services are a genuine constituent of any distributed architecture which facilitate binding attributes to names and then querying this information, i.e., announcing and discovering resources. In the web services domain this functionality is provided by UDDI or some of its semantic extensions/counterparts for semantic-based resource description and discovery. All of these approaches deal with functional aspects, i.e., interfaces, of web services but do not address non-functional properties such as quality-of-service (QoS). However, in a business environment, usually the non-functional properties are actually the first ones to be applied in deciding whether a specific resource will be used and only if the QoS is considered satisfactory, the functional requirements are being looked at. In this paper we address this problem by providing an approach to semantic description and discovery of web services which specifically takes into account QoS. Our approach allows web service providers to describe the functional and QoS properties of semantic web services and users may discover services based on both types of information with results ranked according to their preferences. As QoS specifications by the provider are basically claims, our approach includes a user feedback mechanism which allows the users of a web service to provide feedback on the actually perceived QoS. This information together with information from trusted third parties (rating agencies) is fed in to a robust statistical trust and reputation model, which takes into account attacks such as bad-mouthing, collusion, etc., and then allows us to provide an accurate picture of the actual QoS to user. Our search engine is based on an algebraic discovery model and uses adaptive query-processing techniques to parallelize expensive operators. Architecturally, the search engine can be run as a centralized service for small-scale environments or can be distributed among any number of cooperating registry providers. To enable scalable discovery we devise a peer-to-peer-inspired distribution strategy which enables fault-tolerance and allows registries to maintain full control and confidentiality on the information they provide.