But there are no REST semantics for indicating state. REST is stateless: http://www.ics.uci.edu/~fielding/pubs/dissertation/rest_arch.... I think maybe he's conflating HTTP with REST.
This problem could be solved in a RESTful way by returning a resource that includes all the needed information. I understand he describes that as not being robust, but that doesn't mean it isn't RESTful. In fact fielding acknowledges this very trade-off:
"Like most architectural choices, the stateless constraint reflects a design trade-off. The disadvantage is that it may decrease network performance by increasing the repetitive data (per-interaction overhead) sent in a series of requests, since that data cannot be left on the server in a shared context."
Also, because REVAT URLs are randomly generated the server needs keep track of the resources being pointed to instead of being able to understand it from the semantics of the request. Which works fine right up until you have to scale your application to more than one server. Now you have to deal with the complexity of keeping a distributed system consistent - otherwise those REVAT URLs might sometimes return a 404 - or you're limited to a single centralized link server. These are both scenarios Fielding was trying to avoid by including statelessness as a constraint.