Strange consequences of Axiom of Choice in Zermelo set theory

Recently I read the following quote (for the umpteenth time):

The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma? — Jerry Bona

Normally, the equivalence of these three over ZF is given as a justification for Zorn's lemma, since AC is 'intuitively' true. However, I have always found it lacking because the equivalence crucially depends on transfinite induction via the axiom schema of replacement, which I find unintuitive, unlike the axioms of Zermelo set theory (which lacks both Replacement and Regularity). So my question is:

What are 'counter-intuitive' consequences of AC in ZC (Zermelo set theory)?

I understand that this is not a precise question, but I am looking for examples of the same sort as mentioned here and here. I consider these examples as 'near misses', because while many people consider them counter-intuitive, I do not since they all rely on being able to handle arbitrary real numbers or even sets of real numbers, which is not possible in the first place. Specifically, there is no issue with a conceptual choice function that picks one representative from every equivalence class even if it is not implementable, just as there is no issue with a conceptual oracle machine to solving the halting problem even though it is not implementable.

As for the Banach-Tarski paradox, I do not find it counter-intuitive because we cut up the ball not into nice pieces at all, but instead sets of point dust that can be rearranged. It is not much different from taking the countable set $S = \{ \exp(i{\large \frac{k}{2^m}}) : k,m \in \mathbb{N} \land m2^m \le k < (m+1)2^m \}$ as points in the complex plane and rotating it by $\exp(i)$, which is a rigid transformation of a bounded point set that has just made countably many points vanish (in fact, ordered around the unit circle, every other point has vanished), completely constructively.

Related to this question, based on the iterative conception of sets, we get roughly Replacement for countable sequences as stated by Boolos in the quote here. Thus I am also interested to know any 'counter-intuitive' consequences of AC in ZC plus Replacement for countable sequences.

To sum up some of the discussion in the comments, I think you are greatly overestimating the role of Replacement in applications of the axiom of choice. The vast majority of transfinite induction arguments do not use Replacement in any essential way. One key to many applications is the following theorem of Hartogs (which is valid in Zermelo set theory without Choice):

Theorem: Let $X$ be a set. Then there exists a well-ordered set $W$ such that there is no injection $f:W\to X$.

Proof: Define $W$ to be the set of isomorphism classes of well-orderings of subsets of $X$, ordered by length. A well-ordering of a subset of $X$ is a subset of $X\times X$, and an isomorphism class is a set of such subsets, so $W\subset\mathcal{P}(\mathcal{P}(X\times X))$ and is a set by Separation. Note that the well-ordering of $W$ is longer than any element of $W$, since each element of $W$ is isomorphic to a proper initial segment of $W$ (namely, its own set of proper initial segments). If there existed an injection $f:W\to X$, the ordering on $W$ would give a well-ordering of the image $f(W)\subseteq X$ which has the same length as the well-ordering of $W$. But the well-ordering of $f(W)$ is an element of $W$. This is a contradiction.

This theorem can, for instance, be used to prove Zorn's lemma without Replacement. Given a poset $X$ which is a counterexample to Zorn's lemma, let $W$ be as in the theorem. Now just follow the usual transfinite recursion argument, using $W$ as the index set of the recursion rather than the ordinals. The argument constructs a strictly increasing function $W\to X$, which is in particular an injection. This is a contradiction.

By a similar argument, the theorem can be used to prove the well-ordering principle: using a choice function on nonempty subsets of $X$, just define a function $f:W\to X$ by transfinite recursion which is injective as long as possible (that is, $f(w)$ is different from $f(v)$ for all $v<w$ unless such values $f(v)$ are already all of $X$). Since $f$ cannot be an injection, this means that it must be surjective, and this gives a well-ordering of $X$.

You also mentioned in a comment:

I also find theorems that use the cardinality of the reals to be unintuitive, such as that there is a subset of the plane that intersects every straight line in exactly 2 points.

Results like these do not use Replacement either: they merely use a well-ordering of the reals. Given that a well-ordering of the reals exists, you can take one of minimal length, and then use that well-ordering as a substitute for the cardinality of the reals everywhere.

Just a thought. In ZFC, let $k$ be the first uncountable strong limit cardinal. Then $(V_k,\in)$ satisfies ZC (includung Regularity) but not Relacement. Because with $a_0=\omega$ and $a_{n+1}=2^{a_n}$ we have $k=\sup_{n\in \omega}a_n,$ and we can write a formula of the form $\forall n\in \omega \exists ! x\; (F(x,n)),$ where $F(x,n)$ iff $x=a_n$ when $n\in \omega$, and such that this formula is absolute between $V$ and $(V_k,\in).$

Intuitively the formula "should" define a countable sequence. But $\{a_n\}_{n\in \omega}\not \in V_k$.... I am just wondering whether we could find some more-interesting properties of $V_k$ that make use of the occasional failure of certain countable sequences to exist in $V_k.$ So that, assuming Con(ZFC), these properties would be undecidable without Replacement.