I recently took that same quest. I hired 1 companion, next day I hired 4 more. Immediately I set out to the area where I was told they'd been seen, crossing many frozen rivers and lakes to get there. After many days of fruitless search, finding no signs at all, from a mountain top I spotted what might be them in the distance.
Of course, after traversing the thick woods I had, once again, found no sign of them at all. I stumbled onto and killed, two lynx, a polecat, and a bear while I camped the broad area but never found the outlaws.
Then the first Companion I'd hired notified me he would soon leave, so, I packed up the camp and headed home- only to realize that the warming weather had made all of the ice too brittle to walk over anymore! The few villages in the area had no punts available for trade. I tried with a raft but spent two fruitless days chipping and moving across the water, still with no land in sight. Before I finally decided to trek MUCH farther north to look for fords, two Companions had drowned testing the ice and the others had left me. I don't think they'll ever get home...