The documentation is missing from http://musicbrainz.org/doc/Development/XML_Web_Service/Version_2/Search but is available on http://musicbrainz.org/doc/Search_Server - using the example URLs from the latter on musicbrainz.org (http://musicbrainz.org/ws/2/cdstub/?query=title:Doo, http://musicbrainz.org/ws/2/freedb/?query=artist:Ska-P and http://musicbrainz.org/ws/2/tag/?query=rock) does work, so I guess the glue that was missing for MBS-3840 / SEARCH-248 is actually already there, just the documentation is missing.