The rule of thumb is: defer state from your custom developed services whenever possible, especially when creating agnostic (generically reusable) services. This means that you can have intentionally stateful "system" services that take care of state management in order to alleviate others from having to do so. Also, when your middleware implements WS-* extensions, like context management (WS-Coordination), you will notice that it automatically provides stateful Web services that fulfill this role. Other options for statement management also exist, like the use of middle tier databases or an orchestration engine that will centralize state information along with business process logic.
This was first published in October 2005