Searching through semantic memory involves navigating across clusters of related items, but the current body of work has primarily focused on search within hierarchically structured taxonomic categories (e.g., Animals). The present work explored search behavior via the verbal fluency task in thematic categories, where relatedness is construed via complementary roles in a shared environment, and ad hoc categories, where relatedness is construed via shared service to an external goal. We found strong differences across domains within each type of category, but compared to Animals, responses in thematic and ad hoc categories had higher average phonological similarity and word frequency. Phonology-inclusive process models provided the best account of search in taxonomic categories, but overall model performance was poor for ad hoc categories. There were also important differences in the contribution of lexical sources to within and between-cluster transitions across domains. These results underscore the necessity of exploring lexical search and validating computational models in categorical domains with different compositions and types of relatedness.