Often in conversations with corporate developers, if the subject of the REST architectural style comes up, an immediate concern raised is the principle of the statelessness of the protocol. In the context of real Web services, that protocol is for all practical purposes HTTP. (Another protocol such as SMTP may provide a useful Internet service, but being "on the Web" by definition means it is accessible to HTTP user agents. See RFC 2616 if you are confused about that concept.)
So whether a service deployed using WS-* stack tools is in fact a Web service depends on whether it uses HTTP. If it does, then it can be said to be a service "on the Web" at least in a trivial way. The remarkable thing is how WS-* deployments coerce and overload the HTTP methods, particularly POST and GET, in contradiction to Web standards like RFC 2616. Without being pejorative it is clearly a deliberate design decision to apply HTTP in an off-label manner. When it hasn't been shown that the benefits of a coercive practice are worth the consequences, the term I usually use is gratuitous complexity. Systems should say what they mean and mean what they say.
That's what draws people to REST even when they don't understanding its principles. The hope is that their systems can shed their gratuitous complexities. They would do well to remember Einstein's advice, that things should be as simple as possible, but no simpler. The good doctor recognized that complexity and inelegance in proposed explanations can arise from overly simplistic models just as they can from models that are overly detailed. That is the true elegance of REST, as an articulation of just what it is we aught to be focusing on to get services that will fit well on the Web.