KISS: Use REST always, never SOAP.
I've implemented many Web services using both standards and I can tell you categorically that in hindsight I should have used REST always.
I recently read someone describing REST as a query string. This is incorrect. It's a way to think about the transfer of information. And REST doesn't limit you to 2 or 3 string parameters, like others say. It is in effect limitless in terms of the types and sizes of queries and responses that you can transfer. The reason people get confused about all of this is that browsers limit the amount of data that you can put in the address bar. The HTTP protocol, however, doesn't impose any such limits, so you could easily write a program that sends a GET request that is 10,000 characters long. You won't be able to use a browser to send the same request, but you can't use a browser to send a SOAP request either.
REST is infinitely easier to code, debug, maintain, and, most importantly, document. It's also easier for clients to understand. That's why Amazon, Yahoo, Google, and many others are moving to RESTful services for everything.
REST allows your service to work through firewalls, take advantage of caching, HTTP authentication, and everything else that exists out there to support the Internet. And REST is scalable. The Internet itself is largely RESTful.
REST represents compatibility. You'll never, ever have compatibility issues or client implementation problems with REST. You'll write a server that any client can communicate with, problem-free. Any client written in any code on any operating system, regardless of the server's platform or programming language, will be able to talk to your server. And you can write some clients for REST Web services in 3 lines of code.
RESTful Web services are also the easiest by far to scale. Making a Web service truly RESTful in effect means that you've given your Web service an excellent chance to be the most scalable that it can be. Because RESTful services are stateless, you can simply add more hardware to scale your services.
I never ceased to have problems with SOAP. Even long after services were deployed, I have always needed to tend to issues relating to SOAP. I honestly wonder why SOAP is even considered as an alternative these days. The fact is that there is little or nothing that SOAP can bring to the table that a RESTful solution can't do better. What programs do you know about that go around hunting for services on their own? Why in the world do you need the complexity of the SOAP envelope when you can send or receive a simple XML string with just the data you need? Theoretically, I can see how it would be difficult to publish a RESTful service in a way that a computer program could locate it and use it on its own without human assistance. I can see also other such things that SOAP might make easier. But I've never seen a real application that actually benefits from any of this. If you are a practical thinker that is solution-oriented, you'll find that the SOAP solution brings nothing but problems to most Web services (the exception is when the client and the server are running on the same platform, are otherwise tightly coupled, and are exchanging a small amount of data--exactly the types of restrictions that Web services aim to overcome in the first place).
Every RESTful application I've ever deployed has been a resounding success. I can't say the same for all the SOAP applications I deployed in the past.
Please enlighten me if I'm wrong about any of this.