By now it's a cliche to observe that allegedly "RESTful" web services like Amazon's SimpleDB and the Flickr web service and the del.icio.us web service aren't really RESTful. But there's something about them that makes their creators distinguish them from SOAP-based web services (by calling them "RESTful"), and there's something about those services that users love despite the possibility of, eg. deleting data by accident.
Leonard has come up with a nice classification of real-word "Web services". I think there's one additional distinction that can be made with the degree of hypermedia that's being applied – the "connectedness" described in Leonard's and Sam's book as the low-hanging fruit, and the driving of the application's flow through links as the more advanced concept (as e.g. described by Jim/Savas/Ian).