Of course enclosing a message in a SOAP envelope does not preclude RESTfulness. If the set of messages to which an object responds is a function of its current state then it's RESTful (or at least lead to a RESTful design).
REST isn't even about discoverability. That's just a natural consequence of calling methods that might only exists when an object is in a particular state (i.e. the object creates the methods at runtime).
The difference between REST and (usual) SOAP is the difference between late-binding and "extreme late-binding"[1]
What I meant to say is that in REST, the set of messages to which an object will respond is a function of the object's current state. With SOAP, a URL endpoint always takes the same set of messages (until the code is rewritten or something).