FSM behaving strangely

I concur with Frank. I approximated the same VWF and simulated your design using Stratix and Stratix II devices. At first I thought you may have a setup violation, but it appears the maximum setup time for any register was ~ 3ns. I think there's something amiss. If I had to guess, the design is simulating without any stimulus to those missing input pins. They simply float at X and thus any registers whose input cones depend on those inputs go to X whenever the registers MIGHT depend on the inputs. In fact, if I simply delete those pins from my stimulus, I see what you're seeing.