State machine transitioning into illegal state

I was talking about the sensitivity list for the registers, not the one for the combinational logic in the always @ * block. The sensitivity list for the registers should have only the clock and signals that drive the "asynchronous" inputs to the physical registers (clear, load, etc.--what's available I think varies by device family). If you use one of the register's asynchronous inputs, the timing on that input is covered by recovery and removal, which are similar to setup and hold respectively for the truly synchronous inputs like D and clock enable.

I would expect the only asynchronous input to the state machine registers to be a reset that is itself synchronized to the clock. That is what recovery and removal analysis is typically used for. Positive slack ensures that all registers creating the state code see the reset deassert in the same clock cycle, so they all leave the reset state in the same clock cycle. If more than one state bit can toggle at the exit from the reset state, recovery and removal analysis is critical to make sure the correct combination of bits toggles.