Simon: Keith throws out a complete red herring. I don't see how the RPC spec or the encoding spec are unRESTfull, the only unRESTfull thing in the SOAP spec, is the always POST HTTP binding.
I've been doing some reading on REST. I'm not convinced that REST dictates GET. Here are three quotes from Roy Fielding, the "inventor" of REST:
I'm now convinced that one can architect a system in accordance to the principles of REST and then implement that system using RPC style, HTTP transport, POST binding, SOAP. In fact, I'll go further and state that the GoogleSearch is an instance of this.