This is a wrong question to start with. My request and recommendation to those designing RESTful applications is to never start with the question of whether any given design decision is RESTful or not. After all, REST is an architectural style. An architectural style, on its own, serves no end function.
A healthy discussion around (a) whether a particular aspect of a design is RESTful or not, and (b) the pros and cons of that part of the design not being RESTful is definitely useful. But it is productive to stay away from such discussions when they turn dogmatic.
I have been holding off this post for over a month. But having seen the latest post titled Your Web Service Might Not Be RESTful If… by Paul Sadauskas, I am motivated to publish this (not that his post is dogmatic – it is certainly not). Originally, I was tempted to write this after reading a section titled "Yeah, but is it RESTful?" in Alexandros Marino's paper on RETRO. In my opinion, there is no need for such rationalizations.
This question is common in a number of discussions and articles about REST. There are megabytes of discussions on the web about whether using server-side sessions is RESTful or not, or whether updating a resource via HTTP method POST is RESTful or not, or how to design a certain feature to be RESTful.
There are a few reasons why I think this this is the wrong question to ponder about. My primary reason is that, a question like this often leads to dogmatic interpretations of REST’s interface constraints, preferring form over function.
Secondly, there is no one-size fits all architecture that suits every problem. In cases where your particular use case is specialized and does not either fit REST’s view of client-server applications, or needs to, for business, technical, or even security reasons, implement web services that are contrary to REST’s architectural constraints, not being RESTful may be the right solution. I can give some very compelling examples, but let me leave that for some other time.
It is far more important to learn to know when to apply which aspects of REST, the consequences of violating any of REST's constraints, and the impact your software infrastructure (like caches) has on your application. Rather than pondering whether a given design is RESTful or not, it is better to focus on how to make judicious tradeoffs, and on getting things done.

{ 3 comments… read them below or add one }
Well said.
[Reply]
Nice post. +1 on the thought that its important to implement what makes sense rather necessarily dictated by the book.
I have at times sensed people attempting to coerce practices which didn’t smoothly fit the notion of ReSTfulness into being argued to be ReSTful. I generally prefer to simply document what is not ReSTful, explain the reasons for the choice and not attempt to force a set of architectural choices or interpretations of what ReSTfulness means in order to be 100% ReSTful
[Reply]
How about “Does this use HTTP properly?”?
[Reply]
subbu Reply:
July 21st, 2009 at 4:25 pm
Even for HTTP, there are cases where you may have to make tradeoffs.
[Reply]