I basically agree to Rysc's comment. I can tell, that for me, the Quartus "safe state machine" option works well. It solved all problems, that have existed before introduction of this feature. I didn't yet feel a need to further investigate the involved synthesis details.
I think the RTL simulation point is the key. Safe statement machine isn't an RTL feature. YOu have to perform gatelevel simulation to check the synthesized design.
I'm not sure, if custom encoding may change anything, because I also use VHDL state enumerations for state machines exclusively. But I guess, it doesn't.