I just completed this quest the other day. I think I did it once before, long ago.
My strategy was to search for tracks on the zoomed out map (skill|tracking) in expanding spiral pattern, starting at the center of the indicated area on the map. I tend to use the tracking skill frequently so I think it was fairly high when I started the quest, over 80%. I did notice one small glitch, the villagers sent me looking for a bull, but my character reported that the found tracks belonged to a cow. It turned out to be a bull, after the twigs on the last tracks were set alight and the animal appeared.
I know that my character has a very good relation with the forest spirits, perhaps this is more important than the tracking skill.