Schizophyllum commune, known as the splitgill mushroom, has over 23,000 sexes. Two individuals are sexually compatible based on genes at two sites in their genome. If a pair has matching genes at either location, the pair is not sexually compatible.
I would expect that in this case the mushroom still only has two types of gametes, and hence only two sexes. There's just an added bit of complexity determining whether a particular pair of gametes can produce a new organism.
I can't help but think that this complex system has to have evolved to very precisely control inbreeding rates.
That makes mechanisms to reduce inbreeding even more important.
I'm not familiar with this latter scenario. A man being sterile is nothing like this algae's situation, as it has nothing to do with "pairing," he's simply unable to produce children with anyone.
I don't know, in my experience people are sure picky about procreating with random strangers (and the ethical concerns regarding the output of the study are... significant).
From people I've known undergoing fertility treatments (and from my own limited research), the issue is frequently traceable to a specific cause in one or both partners (although it appears to be unexplained in about 20% of couples who seek treatment, which would be a small subset of the general population).