I'm not sure I know what track degradation you refer to, as I haven't seen a change in years. Since a year or two I've consistently turned down these quests as they're far too time consuming and boring (for me, the player), with a significant risk of failing because you missed the tracks when you visited that (and neighboring) tiles.
Using tracking from the overmap has never been useful for me, regardless of skill. True, there are random reports of tracks detected (that may or may not be found when visiting the tile), but most of the time no tracks are reported even on tiles where I know there should be tracks (such as when I've seen an animal on that tile and go there to look for it).
Furthermore, I wouldn't recommend trying that quest with such a low tracking skill. There just so great a risk that you won't be able to detect the last track with that skill even if you managed to actually find the tile in which the tracks are located and sort of track those tracks.
The times I've succeeded with the quest I've visited every blasted tile in the area (stopping when finding the tracks, of course) by zooming into it and looking around, but if you want to be sure you'll have to walk through every tile in about three different places to ensure you are actually going to get sufficiently close to see the tracks. Also, this can only be done in daylight, as dawn and dusk won't allow you to see enough.