As to the existence of sufficiently good toolkits, that won't save you in the face of vendor bone-headedness. Talking to .NET from a Java stack is still problematic, where either toolkit on its own is apparently fine on its own territory. There's a particularly fine example in MS Exchange Web Services, where getting Java to talk to it over SOAP is so fiddly they're releasing a Java port of their managed API.
You have the SOAP messages which envelopes (sigh) yet another message-level architecture where every request, even at OO level means constructing request-objects with millions of sub-properties, all types fitting an abstract inheritance tree. Which ofcourse is also what you get returned after sending your request. So then you have to start analyzing your response object (again a message-object enveloped in a SOAP-message) and anaylze what class it actually is and the same for all subproperties.
I don't mind SOAP so much, but EWS can really go die in a fire. You can say whatever you want about SOAP in general, but EWS cannot really be used as an example of anything other than itself. I've never seen such a painful and convoluted solution anywhere else.
Even if SOAP had been ditched and the wire-format used had been some sort of RESTFul implementation, it would still be a clusterfuck to use. Blaming SOAP here is IMO a bit misdirected.
I thought it was discoverability which was SOAP's strong point, while ad-hoc solutions like REST which have the bonus of being much more lightweight/terse, lacks this feature.
As for non-standard query-format, with a good toolkit you point to the WSDL and you are done, all your RPC-calls pregenerated for you.
I know SOAP has some issues, that it's a verbose line-format and that recent WS*-additions add complexity faster than you can say "oh shit", but at its root, SOAP really isn't hard to work with if you have a decent toolkit.
If you are hand-rolling your SOAP-layer, you might as well start invoking your database trough telnet and handrolled protocol-code. It makes as much sense.