Search on Mobile Phones (.. and other search papers from CHI 2003) -- "The users seemed to cleverly estimate the navigation effort through links versus via search, and when they expected a long navigation path, they preferred to type in a keyword or two in a search field."
(Mac comments: Via Lou Rosenfeld.)