Right now, the webservice search queries only allows you to use the lucene search syntax mode, which means that you can't make use of the new website search's multi-field query ability.

Compare:
http://www.musicbrainz.org/ws/2/recording?query=we%20will%20rock%20you%20queen (doesn't return any recordings with artist Queen)
http://musicbrainz.org/search?query=we+will+rock+you+queen&type=recording&method=indexed (returns mostly recordings with artist Queen)

Ideally a parameter would be added to disable the advanced/parsed mode and do the same thing as the website default search. Perhaps "...&method=advanced/indexed" to match the website, with advanced being the default?