Here $[5]:=\{0,1,2,3,4\}$ and for sets $O,I$, $O^I$ denotes the set of functions from $I$ to $O$.
The motivation for this question comes from the following axiom of choice "paradox":
Let $f_1, f_2 \in [5]^{\mathbb{N}}$ be unknown functions. Player 1 and player 2 define an equivalence relation $\sim$ on $[5]^{\mathbb{N}}$ where two functions are equivalent if they differ on finitely many inputs. The two players use the axiom of choice to agree on a left-inverse $g$ to the canonical surjection $[5]^{\mathbb{N}}\rightarrow [5]^{\mathbb{N}}/\sim$. Let $g^*$ be the lifting of $g$ to a map $[5]^{\mathbb{N}}\rightarrow [5]^{\mathbb{N}}$.
Player 1 and Player 2 now separate and no longer communicate. They are each tasked with looking at $f_1$ and $f_2$ on various inputs, then guessing the output of one of these functions on an unknown input. If $f_1$ and $f_2$ are generated "randomly", their best chance of success should not exceed $2/5$.
Player 1 asks to see all of $f_1$, computes $g^\ast(f_1)$, then lets $k_1\in \mathbb{N}$ be least such that $g^*(f_1)$ and $f_1$ agree on $\mathbb{N}^{\ge k_1}$. Player 1 then asks to see $f_2$ on $\mathbb{N}^{>k_1}$ which is enough information to compute $g^\ast(f_2)$. Player 1 then guesses that $f_2(k_1)=(g^\ast(f_2))(k_1)$.
Player 2 asks to see all of $f_2$, computes $g^\ast(f_2)$, then lets $k_2\in \mathbb{N}$ be least such that $g^*(f_2)$ and $f_2$ agree on $\mathbb{N}^{\ge k_2}$. Player 1 then asks to see $f_1$ on $\mathbb{N}^{>k_2}$ which is enough information to compute $g^\ast(f_1)$. Player 2 then guesses that $f_1(k_2)=(g^\ast(f_1))(k_2)$.
Clearly for any pair of functions $f_1,f_2$, either Player 1 or Player 2 (or both!) will succeed.
A second paradox removes the ability of the player's to choose which input subset to look at, but requires infinitely many players:
A countably infinite set of players (indexed by $\mathbb{N}$) will tomorrow all receive hats of one of 5 colors (identified with $[5]$) and be able to see the hats of all players indexed by a natural strictly larger than their own. They must all simultaneously guess the color of their own hat. They can make all but finitely many guess correctly tomorrow by agreeing on $g^\ast$ as above.
I'm wondering if there is any input set $S$ on which we can get a paradox that has both aspects - finitely many players and a predetermined set that each player can look at. For $S=\mathbb{N}$, this looks similar to Freling's Axiom of Symmetry so I strongly suspect $S$ should be larger.
The question in the title asks for the strongest version of such a paradox that I could dream existed, but feel free to weaken the assumptions!