After pretty much wasting a spending a whole day reading example WSDL, specs, tutorials and banging my head against the WSDL/SOAP tools you get with .net/mono I am finally getting somewhere.
I downloaded the SOA Editor (registration requires you fill every field, even fax - very annoying) from capescience.
I also managed to get to a point with mono wsdl where I could start to debug by comparing against the googlesearch wsdl
After chatting with gellyfish on irc and cribbing from GoogleSearch WSDL and trying various things out I managed to get mono wsdl to complain about the response rather than the request, from there I was able to use microsoft xsd.exe (via mono) to generate a schema of the result and cut and paste that into the final wsdl, and now it seems to work.. where work equals generating a huge c# file.
Todays lesson: ensure you are using rpc not document mode, which means no literal output - you need to explicitly include the xsd schema of input and output.
Remember WSDL is a fragile thing and if yours doesn't work its because its not-quite-right and expect to spend a lot of time polishing it until its perfect and everything knows exactly what it means, no shortcuts no easy ways.