The annealing approach was a bit over my head, but I was able to come up with a solution that seems to work well for the numbers I'm working with and that may be within reach of others who find this post.
The key was to use a random shuffle of the list rather than trying to walk through the permutations systematically, which becomes impossible for numbers as big as a typical class.
I ran this with a deck of 26 being shuffled and was able to generate 19 pairs in a few minutes. Here's the output, with the number of iterations the loop has been through printed for good measure:
Iterations: 1
Set 0 : [(15, 24), (25, 7), (22, 12), (0, 3), (14, 13), (20, 23), (8, 18), (19, 6), (9, 5), (17, 2), (21, 16), (10, 11), (1, 4)]
Iterations: 2
Set 1 : [(0, 2), (25, 3), (20, 15), (7, 11), (5, 10), (17, 16), (4, 23), (24, 8), (6, 9), (1, 13), (22, 14), (12, 21), (19, 18)]
Iterations: 4
Set 2 : [(8, 0), (14, 19), (17, 1), (7, 3), (15, 11), (10, 21), (9, 18), (4, 12), (23, 5), (24, 2), (22, 6), (13, 20), (16, 25)]
Iterations: 8
Set 3 : [(3, 24), (15, 6), (16, 1), (22, 20), (25, 21), (10, 18), (19, 5), (17, 14), (7, 23), (13, 4), (0, 11), (9, 2), (12, 8)]
Iterations: 9
Set 4 : [(18, 21), (11, 22), (20, 16), (23, 2), (7, 10), (24, 0), (4, 9), (17, 25), (19, 8), (12, 3), (15, 5), (6, 13), (1, 14)]
Iterations: 23
Set 5 : [(1, 7), (20, 3), (8, 22), (23, 0), (15, 21), (14, 6), (18, 5), (9, 25), (19, 13), (12, 17), (16, 4), (24, 11), (10, 2)]
Iterations: 32
Set 6 : [(20, 2), (1, 12), (19, 25), (18, 3), (24, 7), (5, 6), (11, 4), (8, 16), (9, 22), (13, 21), (0, 17), (10, 14), (23, 15)]
Iterations: 66
Set 7 : [(1, 6), (25, 2), (15, 3), (24, 9), (10, 4), (18, 13), (14, 23), (8, 5), (11, 21), (16, 19), (17, 20), (22, 7), (0, 12)]
Iterations: 88
Set 8 : [(25, 5), (21, 14), (10, 24), (17, 9), (1, 23), (8, 13), (0, 4), (18, 22), (12, 15), (6, 3), (20, 19), (16, 11), (2, 7)]
Iterations: 469
Set 9 : [(19, 22), (5, 16), (17, 13), (6, 2), (15, 9), (20, 0), (11, 14), (3, 23), (21, 24), (18, 25), (12, 7), (1, 10), (4, 8)]
Iterations: 877
Set 10 : [(8, 9), (16, 3), (2, 11), (17, 23), (7, 4), (14, 15), (12, 10), (20, 24), (21, 19), (6, 18), (22, 25), (1, 0), (13, 5)]
Iterations: 1363
Set 11 : [(20, 5), (6, 12), (16, 18), (9, 14), (0, 19), (1, 2), (17, 10), (13, 22), (25, 15), (3, 11), (4, 24), (7, 8), (21, 23)]
Iterations: 7435
Set 12 : [(18, 12), (11, 13), (9, 16), (5, 4), (8, 6), (25, 20), (14, 7), (19, 24), (10, 0), (17, 21), (15, 1), (3, 2), (22, 23)]
Iterations: 12008
Set 13 : [(4, 25), (5, 14), (12, 2), (19, 3), (18, 17), (23, 10), (1, 24), (15, 16), (20, 8), (21, 7), (13, 9), (6, 11), (22, 0)]
Iterations: 23082
Set 14 : [(14, 25), (6, 7), (5, 1), (18, 0), (22, 24), (19, 2), (23, 16), (11, 20), (21, 4), (12, 9), (13, 15), (17, 8), (10, 3)]
Iterations: 24293
Set 15 : [(22, 1), (6, 4), (16, 14), (15, 10), (7, 17), (24, 23), (2, 18), (25, 8), (11, 19), (21, 20), (0, 13), (3, 9), (5, 12)]
Iterations: 218369
Set 16 : [(12, 11), (9, 7), (4, 18), (10, 16), (5, 2), (24, 13), (19, 17), (23, 8), (14, 20), (6, 21), (15, 22), (0, 25), (1, 3)]
Iterations: 1080700
Set 17 : [(11, 9), (16, 6), (13, 7), (15, 17), (0, 21), (10, 8), (22, 2), (1, 25), (12, 23), (14, 3), (18, 20), (4, 19), (24, 5)]
Iterations: 6746593
Set 18 : [(23, 18), (15, 7), (17, 3), (25, 24), (22, 5), (12, 19), (1, 21), (4, 14), (11, 8), (9, 10), (13, 2), (20, 6), (0, 16)]
The number of iterations goes up dramatically over time, but it's within workable limits.
Since this solution relies on a random shuffle, there's also some variability in the results. For example, when looking for a class set of 12, I find that some runs appear to get into an impossible corner, where others quite quickly get all 11 possible sets, as the one below did:
Iterations: 1
Set 0 : [(6, 1), (7, 9), (11, 4), (10, 3), (8, 2), (5, 0)]
Iterations: 2
Set 1 : [(1, 3), (10, 11), (9, 8), (5, 7), (0, 6), (2, 4)]
Iterations: 4
Set 2 : [(2, 10), (7, 8), (4, 6), (5, 11), (3, 9), (1, 0)]
Iterations: 15
Set 3 : [(9, 10), (4, 1), (8, 5), (7, 11), (6, 2), (3, 0)]
Iterations: 17
Set 4 : [(11, 9), (8, 1), (6, 5), (7, 3), (4, 10), (0, 2)]
Iterations: 21
Set 5 : [(4, 3), (7, 1), (2, 11), (9, 5), (6, 8), (0, 10)]
Iterations: 38
Set 6 : [(10, 7), (4, 0), (9, 6), (11, 8), (2, 1), (5, 3)]
Iterations: 241
Set 7 : [(4, 7), (11, 3), (9, 2), (0, 8), (6, 10), (5, 1)]
Iterations: 806
Set 8 : [(9, 1), (3, 2), (4, 5), (8, 10), (11, 6), (0, 7)]
Iterations: 1660
Set 9 : [(8, 3), (2, 5), (11, 0), (9, 4), (7, 6), (1, 10)]
Iterations: 9236
Set 10 : [(0, 9), (2, 7), (5, 10), (3, 6), (8, 4), (11, 1)]
Best Answer
Permit me to remark on the connection to Analytic Combinatorics. It is known that all endofunctions on $[n]$ are sets of cycles of labeled trees. This follows from the fact that when we iterate $f$ we obtain a path that terminates in a cycle and is documented in Random Mapping Statistics by P. Flajolet, where the asymptotics are then derived. The construction also appeared at this MSE link. The combinatorial class is then given by
$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{F} = \textsc{SET}(\textsc{CYC}(\mathcal{T})) \quad\text{where}\quad \mathcal{T} = \mathcal{Z} \textsc{SET}(\mathcal{T}).$$
Now in the present case there can be no cycles of two or more elements because the values on those cycles would not fit the condition that $f(f(x)) = f(f(f(x))).$ This leaves sets of trees, with the root of the tree being a fixed point. Observe that any leaf with a path to the root including the root that contains more than three nodes also breaks the requirement that $f(f(x)) = f(f(f(x))).$ This restricts the class of trees to those where the path from every leaf to the root including the root contains at most three nodes. Now to characterize these trees they are first, a singleton node (fixed point) or second, a singleton node (also a fixed point) with a set of subtrees attached to it, which are in turn either leaves or have a set of leaves attached to them. With the combinatorial class $\mathcal{T}$ of these trees we thus obtain
$$\mathcal{T} = \mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1} (\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z})).$$
The desired combinatorial class $\mathcal{F}$ is a forest of these trees given by
$$\mathcal{F} = \textsc{SET}(\mathcal{T}) = \textsc{SET}(\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1} (\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z}))).$$
Observe that the distinction between nodes that have no subtrees attached to them and nodes with a set of subtrees as a feature which appears during the study of the problem givens is not essential here and we may use the convenient fact that
$$\mathcal{E} + \textsc{SET}_{\ge 1}(\mathcal{Q}) = \textsc{SET}(\mathcal{Q}).$$
We thus have for the class in question that it is
$$\mathcal{F} = \textsc{SET}(\mathcal{Z}\textsc{SET}(\mathcal{Z} \textsc{SET}(\mathcal{Z}))).$$
What is happening here is that for rooted trees of height at most $h$ we have $\mathcal{T}_{\le 0} = \mathcal{Z}$ and for $h\ge 1$
$$\mathcal{T}_{\le h} = \mathcal{Z} \textsc{SET}(\mathcal{T}_{\le h-1}).$$
We instantly obtain the EGF
$$F(z) = \exp(z\exp(z\exp(z))).$$
Extracting coeffficients here we find
$$n! [z^n] F(z) = n! [z^n] \sum_{q=0}^n \frac{1}{q!} z^q \exp(qz\exp(z)) \\ = n! \sum_{q=0}^n \frac{1}{q!} [z^{n-q}] \exp(qz\exp(z)) \\ = n! \sum_{q=0}^n \frac{1}{q!} [z^{n-q}] \sum_{p=0}^{n-q} \frac{1}{p!} q^p z^p \exp(pz) \\ = n! \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p [z^{n-q-p}] \exp(pz) \\ = n! \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$
This is the formula that is presented at OEIS A000949. Apparently they chose to simplify by omitting the term for $q=0$ ($q^p=1$ only when $p=0$ but then $p^{n-q-p} = 0$) and extracting the term for $q=n$ (which simplifies to $1$) to get
$$1 + n! \sum_{q=1}^{n-1} \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$