Check manually the field 'Sequence' of each stage (the icon 'gears' on the top right of the column). The number should be different: the lesser the closer to the left. Remember the number.
If you faces the issue again, check the sequence. If it was changed, the most obvious reason is manual interaction. Sometimes users suddenly drag a whole column.
Besides, make sure you do not have stages with the same name for different projects. For example, you have 2 'analysis' stages while they have different sequence: one is bigger, another is lesser than 'to-do'.
UPDATE
A. To change the sequence:
1. Turn on the debug mode (the developer assets in the settings >
dashboard > the bottom right corner)
2. Go to any project
3. Hover you mouse of the top right corner of any column. You
would see the settings icon ('gears')
4. Click 'Edit stage'
5. In the right column bottom you would see the field 'sequence'.
B. You can forbid a user to change columns order by forbidding
changing project stages (project.type). By default internal and
project users have a right only to read those stages. Project
administrators have full rights.
If your stages should be created only once (no frequent changes
are update) you can leave that right only for the super user. To that
end in the debug mode go to the Settings > Technical > Security
Access Rights and search for 'project.task.type manager'. Change its
group to 'Administration > Settings', for example
C. You can have the stage with the same name. It doesn't
contradict their ordering. However, if you have 'Analysis' sequence 1
(project 1), 'To-do' sequence 2 (project 1, project 2), 'Analysis'
(project 2) sequence 3, then for the project 1 n it would be ANALYSIS
> TO-DO and for the project 2 it would be TO-DO > ANALYSIS. You
need just to make sure that both stages ANALYSIS have a lower
sequence than To-DO