For better or for worse "REST" has become something thrown onto API descriptions without really thinking about it. It has become the a buzzword that is used because people associate value with it.

Personally, I think that how useful an API is, and how RESTful it is, are entirely uncorrelated.

Exactly, and this needs to get communicated in a much louder way. There is too much fear that if their API isn't "RESTful" it some how isn't useful or good. We need to get over that thinking.