Here follows the final paragraph of section 4.5 in Jech's Axiom of Choice where he proves that AC is independent from the Ordering Principle in set theory with atoms:
The ordering $<$ of $A$ is in $\mathcal{V}$ since the group $G$ consists of order-preserving permutations and so $\text{sym}(<) = G$. The set $I$ consists of finite subsets of a linearly ordered set and thus can be linearly ordered (lexicographically). Therefore the class $\text{On} \times I$ can be linearly ordered (lexicographically again). And since we have a symmetric one-to-one mapping of $\mathcal{V}$ into $\text{On} \times I$, we obtain a linear ordering $<$ of $\mathcal{V}$, which is a symmetric class. Thus every set can be linearly ordered in $\mathcal{V}$.
Let $A$ denote the set of atoms and $\mathcal{V}$ the permutation model.
I understand this as: there is a certain sentence $\varphi(x, y)$ such that we can prove that $\varphi$ represents a linear order of $\mathcal{V}$. That is, the collection $R$ of $\langle a, b \rangle$ such that $\varphi(a, b)$ forms a relation which satisfies the axioms of a linear order, where $a < b$ if $\langle a, b \rangle \in R$. To show this we use that there is a one-to-one mapping of $\mathcal{V}$ into $\text{On} \times I$ (represented by some formula).
Since in general for a sentence $\psi(x_1, \dots, x_n)$ and a permutation $\pi$ of $A$ we have $\psi(x_1, \dots, x_n) \leftrightarrow \psi(\pi x_1, \dots, \pi x_n)$, it follows that $R$ is symmetric. Proof: for any $\pi$ and $\langle a, b \rangle \in R$ we have $\pi \langle a, b \rangle = \langle \pi a, \pi b \rangle$ and $a < b \Leftrightarrow \varphi(a, b) \Leftrightarrow \varphi(\pi a, \pi b) \Leftrightarrow \pi a < \pi b$, so that $\pi\langle a, b \rangle \in R$. Therefore $\pi [R] \subset R$, but also $\pi^{-1} [R] \subset R \Rightarrow R \subset \pi [R]$; that is, $\pi[R] = R$.
Because $R$ is symmetric, so is every $R_\alpha = R \cap \mathcal{P}^\alpha(A)$; that is, $R_\alpha \in \mathcal{V}$. Also, there will be some $\beta$ such that the linear order $(X, <) \subset R_\beta \in \mathcal{V}$. Therefore, by absoluteness, $\mathcal{V} \models X \text{ can be linearly ordered}$.
I'm really confused. Is this correct? But then I'm not using many of the things Jech mentions, such as that the ordering $<$ of $A$ is in $\mathcal{V}$, or that the one-to-one mapping of $\mathcal{V}$ into $\text{On} \times I$ is symmetric.
The mapping from $\mathrm{On}\times A^{<\omega}$ is amenable. In the sense that every subset is in the permutation model. If you assume some class theory with atoms instead, you get the full map. But for set theory it's not necessarily definable in a reasonable sense internally to the model.
If we assume there is a global well ordering of the kernel, though, then the map is definable.
Your way of understanding is just fine. Your confusion arises from the fact that you're delegating a lot of information to "there is a formula", instead of trying to understand this formula.
The idea is to ask what is the orbit of a set $x$ under the permutations in the group. We can enumerate the orbits (although each orbit may fail to have a well-ordering).
Next we ask what is the minimal support of $x$, and we note that since our permutations are order preserving, fixing pointwise a finite set is the same as stabilising it (i.e., no points are moved outside/into the set).
And so it means that two sets in the same orbit will have the same minimal support if and only if they are equal.
So the formula we use for the linear order depends on $A$ and its linear order, as well as a pre-existing formula which well-orders the entire universe.
The point I raised above is that it is consistent that there is no formula providing a well-ordering of the universe. But in that case we can always fix a well-ordering of a large enough $\mathcal P^\alpha(A)$ and work with that one to linearly order a given set $x$.
Finally, the reason you cannot take the formula defining a well-ordering is that this formula is not stable under your permutations. Indeed, there are two atoms $a,b$ such that $a<b$ in the linear order, but $b<_wa$ in the well-order defined by the formula (simply since $<$ is isomorphic to $\Bbb Q$).
This means exactly that $\pi^n(a)$, where $\pi$ is any order automorphism such that $\pi(a)=b$, will define a strictly increasing countable set, and we can prove there are no such sets.
In this case you can ask yourself, instead, since $A$ can be well-ordered in the "full universe", why is it not well-orderable in $V$? And this well-ordering is definable with a parameter (e.g., itself).
The key problem, which is where Jech is a bit scruffy with the details, is that $\sf ZFC$ does not prove that there is a definable well-ordering. In which case there is no injection from $V$ into $\mathrm{On}\times A^{<\omega}$. But there is still an injection (in $V$) from any set into some $\alpha\times A^{<\omega}$, which is enough for the proof to go through.