Okay next hint then, think about the time that Red says that he saw Yuffie. Unfortunately you're approaching this riddle in an order unlike the way I would recommend, but that shouldn't cause too much problem.
Red saw her approximately 6 hours earlier, so at the point where Nanaki saw Yuffie, they would have been roughly 6 hours away from camp, so Yuffie had been gone for about 6 hours, at night. I SEE! Wait, no... I don't...

I don't understand why Vinny went with Cid... I doubt he knows much about that stuff. :P But since they were working with radios, maybe he was using them to communicate with Red? I don't know how long Cid and Vinny were gone for, but by him saying "it happened while he was asleep" it makes it seem like he's trying to cover his butt. :\