Exactly my experience. Over the years we've tried many different ways of coding state machines and it's very hard to keep them readable. Still we continue to use them, the pros outweigh the cons.

There's a pretty interesting RTOS approach based on state machines (www.state-machine.com, no less) that uses single-stack run-to-completion "tasks". They also have some kind of wizard approach to generate code but I haven't had enough time to evaluate it.

For anyone who finds state machines in HLLs unreadable, try looking at a state machine implemented in ladder logic on a PLC!