This http://stackoverflow.com/questions/3285704/why-does-rest-exist is the question that I want to give an answer to. I am answering here because people keep closing it. Sorry, the post refers directly to issues raised in the question and so won’t make much sense without reading the question first. I would even recommend reading version of the question prior to editing as it shows more clearly the frustration of the poster.
A canary in a coal mine.I have been waiting for a question like this for close to a year now. It was inevitable that this day would come and I am sure we are going to see many more questions like this in the coming months.
The warning signs
You are absolutely correct, it does take longer to build RESTful clients than SOAP clients. The SOAP toolkits take away lots of boilerplate code and make client proxy objects available with almost no effort. With a tool like Visual Studio and a server URL I can be accessing remote objects of arbitrary complexity, locally in under five minutes.
Services that return application/xml and application/json are so annoying for client developers. What are we supposed to do with that blob of data?
Fortunately, lots of sites that provide REST services also provide a bunch of client libraries so that we can use those libraries to get access to a bunch of strongly typed objects. Seems kind of dumb though. If they had used SOAP we could have code-gen'd those proxy classes ourselves.
SOAP overhead, ha. It's latency that kills. If people are really concerned about the number of excess bytes going across the wire then maybe HTTP is not the right choice. Have you seen how many bytes are used by the user-agent header?
Readable URL. Only nouns, no verbs. Yeah, that's easy as long as we are only doing CRUD operations and we only need to access a hierarchy of objects in one way. Unfortunately most applications need a wee bit more functionality than that.
The impending disaster
There are a metric boatload of developers currently developing applications that integrate with REST services who are in the process of coming to the same set of conclusions that you have. They were promised simplicity, flexibility, scalability, evolvabilty and the holy grail of serendipitous reuse. The characteristics of the web itself, how can things go wrong.
However, they are finding that versioning is just as much of a problem, but the compiler doesn't help detect issues. The hand written client code is a pain to maintain as the data structures evolve and URLs get refactored. Designing APIs around just nouns and four verbs can be really hard, especially with RESTful Url zealots telling you when you can and cannot use query strings.
Developers are going to start asking why are we wasting our effort on support both Json formats and Xml formats, why not just focus our efforts on one and do it well?
How did things go so wrong
I'll tell you what went wrong. We as developers let the marketing departments take advantage of our primary weakness. Our eternal search for the silver bullet blinded us to the reality of what REST really is. On the surface REST seems so easy and simple. Name your resources with Urls and use GET, PUT, POST and DELETE. Hell, us devs already know how to do that, we have been dealing with databases for years that have tables and columns and SQL statements that have SELECT, INSERT, UPDATE and DELETE. It should have been a piece of cake.
There are other parts of REST that some people discuss, such as self-descriptiveness, and the hypermedia constraint, but these constraints are not so simple as resource identification and the uniform interface. The seem to add complexity where the desired goal is simplicity.
This watered down version of REST became validated in developer culture in many ways. Server frameworks were created that encouraged Resource Identification and the uniform interface, but did nothing to support the other constraints. Terms started to float around differentiating the approaches, (HI-REST vs LO-REST, Corporate REST vs Academic REST, REST vs RESTful).
A few people scream out that if you don't apply all of the constraints it's not REST. You will not get the benefits. There is no half REST. But those voices were labelled as religious zealots who were upset that their precious term had been stolen from obscurity and made mainstream. Jealous people who try to make REST sound more difficult than it is.
REST, the term, has definitely become mainstream. Almost every major web property that has an API supports "REST". Twitter and Netflix are two very high profile ones. The scary thing is that I can only think of one public API that is self-descriptive and there are a handful that truly implement the hypermedia constraint. Sure some sites like StackOverflow and Gowalla support links in their responses, but there are huge gaping holes in their links. The StackOverflow API has no root page. Imagine how successful the web site would have been if there was no home page for the web site!
You were misled I'm afraid
If you have made it this far, the short answer to your question is those APIs (Netflix and Twitter) do not conform to all of the constraints and therefore you will not get the benefits that REST apis are supposed to bring.
REST clients do take longer to build than SOAP clients but they are not tied to one specific service, so you should be able to re-use them across services. Take the classic example, of a web browser. How many services can a web browser access? What about a Feed Reader? Now how many different services can the average Twitter client access? Yes, just one.
REST clients are not supposed to be built to interface with a single service, they are supposed to be built to handle specific media types that could be served by any service. The obvious question to that is, how can you build a REST client for a service that delivers application/json or application/xml. Well you can't. That's because those formats are completely useless to a REST client. You said it yourself,
you have to make "guesses" as to what will come back across the pipe as there is no real schema or reference document
You are absolutely correct for services like Twitter. However, the self-descriptive constraint in REST says that the HTTP content type header should describe exactly the content that is being transmitted across the wire. Delivering application/json and application/xml tells you nothing about the content.
When it comes to considering the performance of REST based systems it is necessary look at the bigger picture. Talking about envelope bytes is like talking about loop unwinding when comparing a quick-sort to a shell-sort. There are scenarios where SOAP can perform better, and there are scenarios where REST can perform better. Context is everything.
REST gains much of its performance advantage by being very flexible about what media types it supports and by having sophisticated support for caching. For caching to work well though nearly all of the constraints must be adhered to.
Your last point about readable urls is by far the most ironic. If you truly commit to the hypermedia constraint, then every URL could be a GUID and the client developer would lose nothing in readability.
The fact that URIs should be opaque to the client is one of the most key things when developing REST systems. Readable URLs are convenient for the server developer and well structured URLs make it easier for the server framework to dispatch requests, but those are implementation details that should have no impact on the developers consuming the API.
The Twitter API is not even close to being RESTful and that is why you are unable to see any benefit to using it over SOAP. The Netflix API is much closer but it's use of generic media types demonstrates that failing to adhere to even a single constraint can have a profound impact on the benefits derived from the service.
It may not be all their fault
I've done a whole lot of dumping on the service providers, but it takes two to dance RESTfully. A service may follow all of the constraints religiously and a client can still easily undo all of the benefits.
If a client hard codes urls to access certain types of resources then it is preventing the server from changing those urls. Any kind URL construction based on implicit knowledge of how the service structures its urls is a violation.
Making assumptions about what type of representation will be returned from a link can lead to problems. Making assumptions about the content of the representation based on knowledge that is not explicitly stated in the HTTP headers is definitely going to create coupling that will cause pain in the future.