You are correct that the reason comes down to locality, but wrong in the specifics.
An operator is defined to be "local" if it only acts on a region whose diameter is independent of the total system size. But there is an unfortunate ambiguity in the phrase "acts on". If a Hilbert space factorizes into a tensor product $\mathcal{H}_A \otimes \mathcal{H}_B$ (or a subspace of that tensor product, like the bosonic and fermionic Fock spaces), then it seems like the phrase "an operator $O$ only acts on region A" would mean that it never changes the state of subsystem $B$ - that is, for every direct product vector $| a \rangle \otimes | b \rangle \in \mathcal{H}_A \otimes \mathcal{H}_B$, $O(| a \rangle \otimes | b \rangle) = | a' \rangle \otimes | b \rangle$ for some vector $| a' \rangle \in \mathcal{H}_A$. Fermionic ladder operators indeed satisy this property. But this is not what we usually mean by "$O$ only acts on region A". Instead, we mean that $O = O_A \otimes I_B$ for some operator $O_A$ acting on $\mathcal{H}_A$. This is a strictly stronger definition, because it means that the vector $| a' \rangle$ cannot depend on $| b \rangle$, but only on $| a \rangle$. The operator $O$ can't even "know about" the state of system $B$, even if it doesn't change it.
Fermion parity-violating operators don't satisfy this stronger requirement that they must factorize into the tensor product of a local operator and the identity. No matter how far apart sites $i$ and $j$ are, you can't write $a_i = A_i \otimes I_j$ or $a_j = I_i \otimes A_j$ for any single-site operators $A_i$ or $A_j$ - because if you could, then $a_i a_j$ and $a_j a_i$ would both equal $A_i \otimes A_j$, and $a_i$ and $a_j$ would commute rather than anticommute, in violation of the canonical anticommutation relations. (I'm being a bit schematic in my notation by neglecting the rest of the system besides sites $i$ and $j$.) In fact, the support of any fermion parity-violating term must be the entire system, because in order to get the signs right, the operator must "know about" states arbitrary far away even if it doesn't actually change the state of the system on those faraway sites. (This is, for example, why there's no way to write the Jordan-Wigner transformation so as to transform $a_i$ in a finite product of Pauli matrices.)
Whether or not the fact that these formal mathematical ladder operators don't factorize into tensor products with finite support reflects a true lack of locality in the physical particles, is a question that I'll leave to philosophers. But the fact is that practically speaking, physically realistic systems don't seem to be described by parity-violating Hamiltonians.