My first surprise was to discover that a lot of people (including me) just take a few REST characteristics and claims to be "Restfull". In fact this is not a problem, but those people provide and promote something else that REST.
If you have time you could have a look at the Roy Thomas Fielding's phd thesis or you could have a look at the richardson maturity model. To be honest, the link that makes me realize what is really REST is this one : http://roy.gbiv.com/untangled/2008/rest-apis-must-be-hypertext-driven.
The key points of REST :
- ressources
- hypermedia
- server statelessness
In this list it seems thats hypermedia driven application is not well considered (accepted?).
What ever read the previous link if what is preceding seems not clear.
Enjoy!