Automated discovery of web services with desired functionality is an active research area because of its role in realising the envisioned advantages of the semantic web, such as functional reuse and automated composition. Existing approaches generally determine matches by inferring subsumption relationships between a request and a service specification, but may return poor results if service profiles are overspecified or provide only partial information. We present a two-staged consistency-based matchmaking approach where services that potentially match the request are identified in the first stage, these services are queried for concrete information, and finally this information is used to determine the matches. We evaluate our matchmaking scheme in the context of the Discovery II and Simple Composition scenario proposed by the SWS Challenge group. Preliminary evaluation shows that our approach is robust while handling overspecified profiles, does not return false positives, and is able to handle partial information in service and requirements specification.