Through a controlled two-stage experiment, we explore the performance of solution search strategies to resolve problems of varying complexity. We validate theoretical results that collaborative group structures may search more effectively in problems of low complexity, but are outperformed by nominal structures at higher complexity levels. We call into question the dominance of the nominal group technique. Further close examination of search strategies reveals important insights: the number of generated solutions, a typical proxy for good problem-solving performance, does not consistently drive performance benefits across different levels of problem complexity. The average distance of search steps, and the problem space coverage play also critical roles. Moreover, their effect is contingent on complexity:a wider variety of solutions is helpful only in complex problems. Overall, we caution management about the limitations of generic, albeit common rules-of-thumb such as "generate as many ideas as possible”.