One thing to look out for, though: The "animal lost in forest cover" quest is painful enough as it is (or, rather, too painful), and if care isn't taken to ensure the tracks are refreshed during the time the character is fruitlessly searching through the other parts of the search area, the tracks may well be gone by the time the PC stumbles upon the right world tile (and happens to see the correct part of that tile).
Another tedious quest that may be become even worse is the robber one, where you typically find the footprints, but don't actually see the robbers themselves.
Note that I definitely like the idea of track decay itself, so it's a matter of looking out for side effects that can be foreseen.