Previous work indicates that semantic categorization decisions for nonexemplars (e.g., deciding that TURBAN is not an animal name) are faster for high-frequency words than low-frequency words. However, there is evidence that this result might depend on category size. When narrow categories are used (e.g., Months, Numbers), there is no frequency effect for nonexemplars. This result is confirmed, and is explained in terms of a category search model, which allows a ''No'' decision to be generated without access to the lexical entry for the target word. This explains the absence of a frequency effect, but not the presence of a strong masked repetition priming effect, which is assumed to have a lexical source. It is shown that this effect may not be lexical, since nonwords also show similar priming. Both of these priming effects disappear when a larger category is used. This pattern of results is explained on the assumption that category search is only possible with small categories, and that tentative category decisions are generated for the unconsciously perceived prime, which leads to a marked response congruence effect.