This warning is triggered if you select BOTH for the Most Or Least Similar parameter when the Number Of Results is larger than half the number of Candidate Features. For the BOTH option, all candidates are ranked from most to least similar. Then the least similar half are reranked from most to least dissimilar.
Any given solution match in the Output Features will either be a solution that is most similar or least similar to the target Input Features To Match; a single solution cannot be both. Consequently, the maximum Number Of Results possible when the BOTH option is selected for the Most Or Least Similar parameter is half the number of Candidate Features.