Mutualism based on reciprocal exchange of costly services must avoid exploitation by “free-rides”. Accordingly, hosts discriminate against free-riding symbionts in many mutualistic relationships. However, as the selective advantage of discriminators comes from the presence of variability in symbiont quality that they eliminate, discrimination and thus mutualism have been considered to be maintained with exogenous supply of free-riders. In this study, we tried to resolve the “paradoxical” coevolution of discrimination by hosts and cooperation by symbionts, by comparing two different types of discrimination: “one-shot” discrimination, where a host does not reacquire new symbionts after evicting free-riders, and “resampling” discrimination, where a host does from the environment. Our study shows that this apparently minor difference in discrimination types leads to qualitatively different evolutionary outcomes. First, although it has been usually considered that the benefit of discriminators is derived from the variability of symbiont quality, the benefit of a certain type of discriminators (e.g. one-shot discrimination) is proportional to the frequency of free-riders, which is in stark contrast to the case of resampling discrimination. As a result, one-shot discriminators can invade the free-rider/non-discriminator population, even if standing variation for symbiont quality is absent. Second, our one-shot discriminators can also be maintained without exogenous supply of free-riders and hence is free from the paradox of discrimination. Therefore, our result indicates that the paradox is not a common feature of evolution of discrimination but is a problem of specific types of discrimination.