Time and time again I've found the following classification useful for thinking about REST and web-APIs in general: http://www.nordsc.com/ext/classification_of_http_based_apis....
Most of the stuff people are describing here as REST would be classified as HTTP-based Type I/II according to the above resource.