For documenting message flow, I have found that state machines and sequence diagrams each have their place. State machines are better at describing the decisions that change the state of a system. Sequence diagrams are better at describing the messages that implement a specific element of a protocol.
Since I like to use Doxygen for internal documentation anyway, and it likes to draw call graphs and other figures with GraphViz tool dot, I started using dot to document my state machines. Since Doxygen has a syntax for including a dot language directly in the source code (and even allows hyperlinks from elements in the drawing to other pages of the generated documentation) this has been really convenient. Recently, Doxygen grew explicit support for sequence diagrams expressed with mscgen, allowing both styles of diagram to be used.
Having the figures expressed in a reasonably natural way directly in the source code makes them a lot more likely to be maintained than if they were drawn externally in Visio or some other drawing tool.