When I want to find a "Big" Web service (WS-*/WSDL based) of required functionality I can simply google for ".... filetype:wsdl" because Google indexes also WSDL definitions. Or I can simply use some registries that already crawled the Web for WSDL definitions for me, e.g. SeekDa.com or ServiceFinder.
When I want to find RESTful Web service (RESTful Web API) I may count only on the community, because it is not possible to distinguish between URI of RESTful Web service and other Web resources (e.g. Web sites URLs) and hence any focused crawler cannot tell for 100% sure: this is URI of RESTful Web service. So, I come e.g. to the ProgrammableWeb.com and I hope someone already used/found the service I'm looking for and registered it there.
Recently, I was looking for the Web service for abbreviation expansion. I couldn't find it in portals like ProgrammableWeb, because no-one has put it there. Finally I was forced to browse through several abbreviation dictionaries sites, dig and drill there and I finally found Abbreviations.com Web service API in RESTful form. That took me a lot of time!
Is there any other Way to discover RESTful Web services on the Web?
The REST ideal is that services are as consumable as Web Pages are, they don't need registries. [Got to admit I don't fully "get" the implications of this RESTful world, no WSDL, no registry feels like riding a bike with no stabilisers.]
In the old Web, pre-Google, how did we find pages? Effectively word-of-mouth and a few key starting points. REST services so far as I can see are pretty much in the pre-Google stage.
I don't agree that "it is not possible to distinguish between URI of RESTful Web service and other Web resources" - if we follow the link we get certain types of content application/xml and application/json would be pretty strong indicators wouldn't they?