As a consultant who has talked at conferences on APIs and is brought in to explicitly fix these kind of issues I have seen a lot of this too but correct REST APIs do exist. I know because my team builds them.
You're experience is anecdotal and as is mine. But just because a lot of people assume REST is something it isn't doesn't mean REST is inferior to SOAP.
> Re: statefulness ("order matters")
My order matters comment had nothing to do with statefulness. I mean in the XML. In SOP this might work:
<order>
<token>ABC</token>
<price>19.95</price>
</order>
<order>
<price>19.95</price>
<token>ABC</token>
</order>
Granted that is not a limitation of SOAP but more XML schemas in general. Json is more likely to be order of values agnostic.
But to play devil's advocate I can see the argument where if you are using SOAP to make multiple RPC calls in the same envelope than order is important.
Moreover, you could design your XML Schema such that both variants are accepted (using XSD "all-groups"), though typically record-like data structures are indeed described using XSD sequences which would cause the issue you mentioned. Again I agree XML/XSD isn't a great payload/schema mechanism for data structures such as maps; after all SGML/XML was invented for encoding text. It's being used because it was the first mechanism on the scene, and it continues to be used because it's still much more capable and mature/established in terms of data validation than anything JSON, especially for protocols used in communication with external partners/banks/authorities.
Re: statefulness ("order matters"): there are intrinsical stateful processes that aren't represented adequately by a REST service. Think of a basic "Purchase Order" resource representing purchased items on an e-commerce website. You generally can't add and delete line items freely once you have placed your order, but you may cancel individual items (unless they're already physically on your way), you may RMA items, etc. Representing this as a flat "Purchase Order" resource with GET, POST, DELETE, PUT primitives is useless as it isn't telling your web shop front-end developers what actions are available at any one time.