Hi,
The web service API does a normal Lucene search query behind the scenes. It's my understand that, as from 2.1, you can search a WCM staging store so executing this search via the web service API should work.
It's defiantly worth a try, lets us know how you get on.
Cheers,
Roy