The global computational grids bring together distributed computation/communication resources. Beyond this, we envision the emergence of global 'service grids', which provide a 'market' of application-level distributed services for clients to discover and to request. In this paper, we study the issue of wide-area service discovery in service grids. We start with an existing basic wide-area service discovery framework. The framework adopts a scalable architecture consisting of a hierarchy of Discovery Servers. We then identify problems with the basic framework, and propose our enhancement of query responsiveness and QoS awareness. The key techniques we introduce include: (1) the addition of QoS feedback capability to clients; and (2) the caching and propagation of discovery results with QoS feedbacks in the discovery server hierarchy. With these techniques, the enhanced service discovery framework will be faster in finding qualified service providers. Further-more, it will select a 'good' (with respect to the QoS to be delivered) service provider for each querying client, based on QoS feedbacks.