“You always select the parent last.”
It doesn’t parent to the last selected, it parents to the active object.
It is only true if you are selecting objects one at a time, because this makes it the active object; When you box select, or shift select (in the outliner) the active object is not changed, thus making it possible to end up parenting the selected objects to a non-selected object.
If anyone ended up parenting to the wrong object during this exercise, this could be the reason.