I read Andrew Hallam's post about REST Abuse last month, and nodded: right, REST != not SOAP. There's more to it. I've spent the past two days programming WMS and WFS clients, and have a little more to add to his thread.
Look at the specs and you'll see that WMS and WFS are aimed at a number of possible distributed computing platforms (DCP). For the enterprisey there is a SOAP DCP. Operations which can't or won't enter the 21st century could use a CORBA DCP. Howard Butler might be willing to scope out an ICE DCP for you. The one DCP you're going to encounter in the wild is named HTTP.