For any function $g: \mathbb{Z}_{>0} \rightarrow \mathbb{Z}_{>0}$ and any subset $X \subset \mathbb{Z}_{>0}$, we define $g(X) = \{ g(x) : x \in X \}$. We have that the image of $f_{X}$ is $f_{X}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \setminus X$. We now show a general lemma about the operation $*$, with the goal of showing that $*$ is associative.

Lemma 1. Let $X$ and $Y$ be finite sets of positive integers. The functions $f_{X * Y}$ and $f_{X} \circ f_{Y}$ are equal.

*Proof.* We have
$$f_{X * Y}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \setminus (X * Y) = (\mathbb{Z}_{>0} \setminus X) \setminus f_{X}(Y) = f_{X}(\mathbb{Z}_{>0}) \setminus f_{X}(Y) = f_{X}(\mathbb{Z}_{>0} \setminus Y) = f_{X}(f_{Y}(\mathbb{Z}_{>0}))$$
Thus, the functions $f_{X * Y}$ and $f_{X} \circ f_{Y}$ are strictly increasing functions with the same range. Because a strictly increasing function is uniquely defined by its range, we have $f_{X * Y} = f_{X} \circ f_{Y}$.

Lemma 1 implies that $*$ is associative, in the sense that $(A * B) * C = A * (B * C)$ for any finite sets $A, B$, and $C$ of positive integers. We prove the associativity by noting
$$\begin{gathered} \mathbb{Z}_{>0} \setminus ((A * B) * C) = f_{(A * B) * C}(\mathbb{Z}_{>0}) = f_{A * B}(f_{C}(\mathbb{Z}_{>0})) = f_{A}(f_{B}(f_{C}(\mathbb{Z}_{>0}))) \\ = f_{A}(f_{B * C}(\mathbb{Z}_{>0})) = f_{A * (B * C)}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \setminus (A * (B * C)) \end{gathered}$$
In light of the associativity of $*$, we may drop the parentheses when we write expressions like $A * (B * C)$. We also introduce the notation
$$X^{* k} = \underbrace{X *(X * \cdots *(X *(X * X)) \ldots)}_{X \text{ appears } k \text{ times }}$$
Our goal is then to show that $A * B = B * A$ implies $A^{* b} = B^{* a}$. We will do so via the following general lemma.

Lemma 2. Suppose that $X$ and $Y$ are finite sets of positive integers satisfying $X * Y = Y * X$ and $|X| = |Y|$. Then, we must have $X = Y$.

*Proof.* Assume that $X$ and $Y$ are not equal. Let $s$ be the largest number in exactly one of $X$ and $Y$. Without loss of generality, say that $s \in X \setminus Y$. The number $f_{X}(s)$ counts the $s^{th}$ number not in $X$, which implies that
$$\begin{equation*} f_{X}(s) = s + | X \cap \{ 1, 2, \ldots, f_{X}(s) \} | \tag{1} \end{equation*}$$
Since $f_{X}(s) \geqslant s$, we have that
$$\{ f_{X}(s) + 1, f_{X}(s) + 2, \ldots \} \cap X = \{ f_{X}(s) + 1, f_{X}(s) + 2, \ldots \} \cap Y$$
which, together with the assumption that $|X| = |Y|$, gives
$$\begin{equation*} | X \cap \{ 1, 2, \ldots, f_{X}(s) \} | = | Y \cap \{ 1, 2, \ldots, f_{X}(s) \} | \tag{2} \end{equation*}$$
Now consider the equation
$$t - | Y \cap \{ 1, 2, \ldots, t \} | = s$$
This equation is satisfied only when $t \in [ f_{Y}(s), f_{Y}(s+1) )$, because the left hand side counts the number of elements up to $t$ that are not in $Y$. We have that the value $t = f_{X}(s)$ satisfies the above equation because of (1) and (2). Furthermore, since $f_{X}(s) \notin X$ and $f_{X}(s) \geqslant s$, we have that $f_{X}(s) \notin Y$ due to the maximality of $s$. Thus, by the above discussion, we must have $f_{X}(s) = f_{Y}(s)$.

Finally, we arrive at a contradiction. The value $f_{X}(s)$ is neither in $X$ nor in $f_{X}(Y)$, because $s$ is not in $Y$ by assumption. Thus, $f_{X}(s) \notin X * Y$. However, since $s \in X$, we have $f_{Y}(s) \in Y * X$, a contradiction.

We will use Lemma 1 from Solution 1. Additionally, let $X^{* k}$ be defined as in Solution 1. If $X$ and $Y$ are finite sets, then
$$\begin{equation*} f_{X} = f_{Y} \Longleftrightarrow f_{X}(\mathbb{Z}_{>0}) = f_{Y}(\mathbb{Z}_{>0}) \Longleftrightarrow (\mathbb{Z}_{>0} \setminus X) = (\mathbb{Z}_{>0} \setminus Y) \Longleftrightarrow X = Y, \tag{3} \end{equation*}$$
where the first equivalence is because $f_{X}$ and $f_{Y}$ are strictly increasing functions, and the second equivalence is because $f_{X}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \setminus X$ and $f_{Y}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \setminus Y$.

Denote $g = f_{A}$ and $h = f_{B}$. The given relation $A * B = B * A$ is equivalent to $f_{A * B} = f_{B * A}$ because of (3), and by Lemma 1 of the first solution, this is equivalent to $g \circ h = h \circ g$. Similarly, the required relation $A^{* b} = B^{* a}$ is equivalent to $g^{b} = h^{a}$. We will show that
$$\begin{equation*} g^{b}(n) = h^{a}(n) \tag{4} \end{equation*}$$
for all $n \in \mathbb{Z}_{>0}$, which suffices to solve the problem.

To start, we claim that (4) holds for all sufficiently large $n$. Indeed, let $p$ and $q$ be the maximal elements of $A$ and $B$, respectively; we may assume that $p \geqslant q$. Then, for every $n \geqslant p$ we have $g(n) = n + a$ and $h(n) = n + b$, whence $g^{b}(n) = n + a b = h^{a}(n)$, as was claimed.

In view of this claim, if (4) is not identically true, then there exists a maximal $s$ with $g^{b}(s) \neq h^{a}(s)$. Without loss of generality, we may assume that $g(s) \neq s$, for if we had $g(s) = h(s) = s$, then $s$ would satisfy (4). As $g$ is increasing, we then have $g(s) > s$, so (4) holds for $n = g(s)$. But then we have
$$g(g^{b}(s)) = g^{b+1}(s) = g^{b}(n) = h^{a}(n) = h^{a}(g(s)) = g(h^{a}(s))$$
where the last equality holds in view of $g \circ h = h \circ g$. By the injectivity of $g$, the above equality yields $g^{b}(s) = h^{a}(s)$, which contradicts the choice of $s$. Thus, we have proved that (4) is identically true on $\mathbb{Z}_{>0}$, as desired.

Comment 2. We present another proof of Lemma 2 of the first solution.

Let $x = |X| = |Y|$. Say that $u$ is the smallest number in $X$ and $v$ is the smallest number in $Y$; assume without loss of generality that $u \leqslant v$.

Let $T$ be any finite set of positive integers, and define $t = |T|$. Enumerate the elements of $X$ as $x_{1} < x_{2} < \cdots < x_{n}$. Define $S_{m} = f_{T * X^{*(m-1)}}(X)$, and enumerate its elements $s_{m, 1} < s_{m, 2} < \cdots < s_{m, n}$. Note that the $S_{m}$ are pairwise disjoint; indeed, if we have $m < m'$, then
$$S_{m} \subset T * X^{* m} \subset T * X^{*(m' - 1)} \quad \text{and} \quad S_{m'} = (T * X^{* m'}) \setminus (T * X^{*(m' - 1)})$$
We claim the following statement, which essentially says that the $S_{m}$ are eventually linear translates of each other:

Claim. For every $i$, there exists some $m_{i}$ and $c_{i}$ such that for all $m > m_{i}$, we have that $s_{m, i} = t + m n - c_{i}$. Furthermore, the $c_{i}$ do not depend on the choice of $T$.

First, we show that this claim implies Lemma 2. We may choose $T = X$ and $T = Y$. Then, there is some $m'$ such that for all $m \geqslant m'$, we have
$$\begin{equation*} f_{X^{* m}}(X) = f_{Y * X^{*(m-1)}}(X) \tag{5} \end{equation*}$$
Because $u$ is the minimum element of $X$, $v$ is the minimum element of $Y$, and $u \leqslant v$, we have that
$$\left( \bigcup_{m = m'}^{\infty} f_{X * m}(X) \right) \cup X^{* m'} = \left( \bigcup_{m = m'}^{\infty} f_{Y * X^{*(m-1)}}(X) \right) \cup (Y * X^{*(m' - 1)}) = \{ u, u + 1, \ldots \}$$
and in both the first and second expressions, the unions are of pairwise distinct sets. By (5), we obtain $X^{* m'} = Y * X^{*(m' - 1)}$. Now, because $X$ and $Y$ commute, we get $X^{* m'} = X^{*(m' - 1)} * Y$, and so $X = Y$.

We now prove the claim.

*Proof of the claim.* We induct downwards on $i$, first proving the statement for $i = n$, and so on.

Assume that $m$ is chosen so that all elements of $S_{m}$ are greater than all elements of $T$ (which is possible because $T$ is finite). For $i = n$, we have that $s_{m, n} > s_{k, n}$ for every $k < m$. Thus, all $(m - 1) n$ numbers of the form $s_{k, u}$ for $k < m$ and $1 \leqslant u \leqslant n$ are less than $s_{m, n}$. We then have that $s_{m, n}$ is the $((m - 1) n + x_{n})^{\text{th}}$ number not in $T$, which is equal to $t + (m - 1) n + x_{n}$. So we may choose $c_{n} = x_{n} - n$, which does not depend on $T$, which proves the base case for the induction.