I second this approach. The only state my behavior classes hold are injected dependencies.

The only caveat to this approach is that for some cases you will need a state accumulator of some sort. But those state manipulations are isolated and easy to deal with.