Strange State Machine Compilation - Compiler Bug?

The two descriptions (with and without the explicit else) may have equivalent behavior but they don't create equivalent initial netlists during elaboration. In the explicit else case, the next state logic is fed by constants. Omit the else and the logic is fed by the current state register, creating feedback in the data path for the next state logic. Think of each IF statement as creating a MUX. In the first case, the MUX has two constant inputs. In the second case, the MUX has one constant input and one non-constant input - the current state register.

Whenever you start from two different netlists, you aren't guaranteed identifcal results. The synthesis engine could be happier optimizing constant inputs. If your netlist has a feedback in the data path, it may trigger a different set of optimizations that produce a different result, possibly better or possibly worse or possibly equivalent.

If you notice potential for significantly optimizing a real example, file a support request with Altera.