Having used both REST style programming and SOAP I see that the difference is how the semantics of the message properties (metadata?) are specified. The ability to specify strongly typed message properties in a well defined and standard format (WSDL) is what separates REST from web services for me. If I am working in a closed community with a high degree of communication and a low rate of change in messaging semantics then REST is fine. However if you are working in a network that participants that are changing independently and there is a poor communication (i.e. people in different organizations that do not even know each other) then web services provides the common framework to express your messaging semantics.
As an example this is a link to POST WSDL for Grand Central that I created. Looking at the WSDL is can be seen that the headers are strongly typed while the message body is a simple XSD:ANY. This allows a user to post any message to Grand Central and route it to its destination using nothing more that the message properties. It is optional to add a strongly typed message.
This approach allows significant extensions through adding more message headers, the second example is STORE WSDL. This example takes an arbitrary message and either stores it in an XML Store or queries the XML Store with XPath gets the results. The only major changes to the wsdl are a new header addressed to the XMLStore service and a new destination. While I freely admit that the WSDL needs some work and some better comments the intent is fairly clear, and with come TLC could be very clear and obvious. As in both cases the message is a XSD;ANY there is a high degree of loose coupling as neither the recipient or sender needs to have apriori knowledge (if they want they can) but the semantics of the message delivery are still well defined. The Grand Central POST Header is an early version of WS-Addressing and WS-ReliableMessaging, and WS-Security is also supported, therefore the message properties are very strongly typed and defined in a way that everyone can read and more importantly understand. This is not possible in REST systems.
To create loosely coupled systems we need to be able to interact at the messaging level and specify the shared semantics as tightly as possible while keeping the business interactions as loosely coupled as possible. Used properly Web Services does this.
