Statefullness is another challenge in most penetration tests. In most penetration tests, simple capture-replay tests around known vulnerabilities and simple use cases built around commonly used features might give a good coverage in attack surface, and some confidence in known issues in legacy specifications. But in real life, protocols such as SOAP/XML applications often come in complex state-diagrams with deeply nested interdepencencies between messages and sequences. A simple traffic capture fuzzer might not be enough to go deep enough in the protocol message flows. A simple method for risk analysis in complex protocols is looking at them from traffic analyzers. If the message flow exceeds just few messages back and forth, then you know the complexity of that protocol is probably beyond any manual analysis.
So next time when someone claims they do fuzzing or any other form of security testing, ask them how they do it. Look at how they try to explain test coverage. And especially require them to provide a measurable definition on what was tested, and what was not. If someone claims they do 100% coverage, you will know they are lying.