Yea, this is a "hard" quest... in the sense of being hard for real-life reasons, rather than game reasons. I had quite the annoying adventure with it:
https://www.unrealworld.fi/forums/index.php?topic=841.0Things like smoke are good ideas generally for the game, but probably wouldn't be something added just for this quest. Once in the game though, it would be really good.
I like the idea of being able to ask nearby villagers a lot. I actually went to a village to try this, hoping it was part of the quest. I would prefer it if quests could be solved different ways depending on a character's strengths. Getting information, or even someone to lead you to them should cost you some goods. That works for a talented craftsman/trapper. Alternatively, more tracks (as you say) should be good for the skilled woodsman type character. It should be about using game skills, not trying your patience in the real world.
Similarly, the robbers should be moving around more looking to rob someone. I mean, they *are* robbers. That would leave more tracks.
All that being said, the reward for the quest is huge... so if it is made a little bit easier, I wouldn't mind if the reward was cut a bit. Also, the annoyingness of it, made it feel very satisfying.