This is probably the worst quest of them all, and the only one I've had to give up (not counting early robber quests), though I've been successful a number of times.
If you DO succeed, please note whether the tracks are described as ram tracks or sheep tracks (or even ewe tracks) and, if the latter, send a save to Sami. I've had this quest where the tracks were from the incorrect gender of the animal, and Sami would like to examine such a situation (I didn't have a save available).
It is currently not known whether you "only" have to search the forest parts of the area ("forest cover" indicates it should be the case). There's no verified case of the animal sought being found in open terrain, but absence of proof is not proof of absence...
I've tried using tracking on the zoomed out map, but gave up that as it increased the search time by 50% or so and is very unreliable normally (looking for e.g. Njerps you've seen in the distance, or animals you're chasing).
As you noted, spruce infested terrain is horrible to find anything in, and the tracks definitely don't cover a huge part of the tile they're in, so it's quite possible to pass them by.
The method I've used is my standard technique for finding most area quest targets: zig-zag over the area, zooming into each tile, look forward, look backwards, zoom out, move one tile,... and turn at the edge and advance one line. That takes something like 2-5 days depending on light conditions (and pray for absence of precipitation, as the animation is murder on the eyes when staring intently at the screen looking for faint details for hours! [I'd consider temporarily hack the image file to save my eyes the next time I get this quest]).
However, as noted, that method has failed once.
An alternative method I have used only for terrain boundary quests where the target is in spruce infested terrain is to move along the border on the spruce side such that I can just make out the other terrain to the side. It might be that this method, zig-zagging on the zoomed in map is required to have a good chance of finding the tracks, but that's a very time consuming task for the player (I'm not sure it takes longer or a shorter time for the character). I'm fairly sure it won't give you a 100% chance to see the tracks anyway, as the distance at which you can see tracks is limited, in particular when the light conditions and weather are not ideal.