Is there an exhaustive, searchable catalog of all GIS web services (e.g. OGC WMS/WFS, REST, SOAP)?
GeoNetwork Opensource and the Esri Geoportal Server are two open source and free technologies that can be used to build Catalog Services for spatial information, and are both a great start.
However, I think both could do with more work on usability.
For example, Catalog Services from the Esri Geoportal Server can be accessed from ArcGIS for Desktop to discover OGC WMS services. There is also an open source CSW Client to have ArcGIS for Desktop bind to and display those WMS services that has been shown to work at Is there public OGC Catalog Service (CSW) available which lets ArcGIS for Desktop with CSW Client Add (WMS) To Map?.
On top of technological issues there are of course administrative issues around who can afford to create and maintain a comprehensive catalog of OGC and other GIS web services. I suspect such a Catalog will need to be a federation of catalogs rather than a centalised monolith.
As an aside, I posted an ArcGIS Idea recently to encourage Esri to Publish public test URLs for each OGC web service supported by ArcGIS but it is yet to take off.
The best search engine for WMS and other OGC web services I found so far is http://spatineo.com.
It works like a google search for geospatial web services. The main advantage of spatineo.com is that it shows info about the service status (this is very important information because many WMS servers are down and the WMS URLs often change). It also provides info if the service has any access restrictions (like "only for registered users")
The free WMS, WFS, WMTS and Esri Rest MapServer search engine Spatineo Directory has recently moved into it's own sub-site http://directory.spatineo.com/
As already mentioned, it's especially useful to developers looking for reliable spatial web services due to current status and historical availability statistics for each service. There are currently more than 30 000 services listed with almost 700 000 layers or provided feature types listed.
Disclaimer: I'm the CTO and one of the founders of Spatineo.