There is no builtin restriction that would prevent the creatures from being able to walk by crossing their legs over. However, walking that way is much more complex and requires a very fine tuned brain that is able to perfectly balance the whole creature during the transition between legs.
Therefore it's much more unlikely that a creature will learn how to do that in a short period of time. Instead, they will optimize their behaviour towards a local maximum where their strategy of walking still gets them moving forward at a certain speed (most likely not as fast as the 'obvious' way they should be doing things) without the need to worry a whole lot about balancing all the time.
You can always get lucky with a creature that is really good at walking using a highly complex movement pattern, it's just fairly unlikely to happen.