I believe there are also single-celled eukaryotes which have more than two mating types.
I think the key is that you have to have a system where a third mating type makes sense. Having fallen into the basin of attraction of anisogamy, and then later sexual differentiation of reproductive anatomy, it’s much harder to develop a new sex that could reproduce with existing males and females (but not itself).
The way the fungal system that leads to the claim of over 20,000 mating types for Schizophyllum commune is similar to how our pheremones (purportedly?) work; you just want to find someone who smells different (i.e., has a different set of MHC) from you, and there are many ways to have different MHC combinations. If someone develops a new one—good! They smell different than everyone (except their own children) and so they never end up stuck with a distantly related potential mate who nevertheless smells too much like them, and this improves their reproductive success until the new MHC is widespread in the genepool. Additionally (in the case of MHC but not mating types) there is purportedly actual immune benefits which drive this, in addition to the generally beneficial encouragement of “out-crossing”.