Robots that search for objects on their own must decide what to do when the search fails, and how they signal that failure to a human partner can determine whether the interaction turns into collaboration. Prior work on human–robot interaction has studied nonverbal help-seeking and social gaze separately, but rarely compares gaze against a matched verbal failure signal inside a live, real-time embodied search task. We present an embodied dialogue system, built on the Retico incremental processing framework, where the Cozmo robot searches for a specified object and signals failure either verbally or through gaze towards the human partner. We first compare a rule-based planner against a vision-language model (VLM) planner that reasons over scene semantics, finding that the VLM planner succeeds far more often (87.2% vs. 65.9%). We then test whether gaze can close this gap without adding reasoning capability to the rule-based planner. Adding gaze as the stuck signal raises success to 87.87%, matching the VLM planner, while a verbal stuck signal only raises it slightly (68.75%). Results further show that this effect is largely implicit: participants helped more in the gaze condition without consistently reporting that they felt invited to do so. Our findings suggest that gaze can substitute for reasoning capability a robot lacks, helping it elicit assistance from a human partner.