You are vastly oversimplifying when you say "with REST you just have to figure out a URL". Try integrating with a service that takes only custom HTTP verbs with multipart/form-data but because there's no standard way to send an array in HTTP you have to append some parameter multiple times but in the right order. There's some vague attempt at using OAuth for authentication, but it doesn't work with any of the libraries you are used to. Oh, and the service returns a 503 some of the time, which (according to the rambling hacked up docs for this API) means you should retry your request in 10 seconds. No, it's not always trivial.
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.
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.