Nice post. The single biggest criticism I usually level at REST implementations is the lack of HATEOAS - the discoverability aspect of REST is about more than just an easily understood URI. As the author of this post states in his 2nd bullet point (emphasis mine): "It’s expressive, REST paths and CRUD requests are easy to understand _and hypermedia makes it easy to navigate_" It's that second part that so many implem…
I agree that this is often glossed over. In fact I can't think of any framework implementation that provides it. About the best example I can think of is the Atom publishing protocol where a service links to it's publishing URLs and a feed can provide pagination through hyperlinks. But still it is not a particularly sophisticated example, do you know of any others?
If you can implement your service entirely with existing formats, that could make things much simpler. But the only kind of hypermedia for machine data access that I've ever heard of is RDF, and there is nothing simple about that.