For me, the way i do these "Find x place near y place" is to check the actual circle the quest leaves on your map and then narrow it down to tiles in the wilderness map through walking and checking the map often. Once i have the "circle" identified i then proceed to find out what places inside the circle match the description that was given to me. This way makes me find the place i was told about basically 2/3 of the time.
On the other hand, i agree that finding the lost animals is annoying, but mostly because of how the tracks work. One time i had this same quest where i had to find a sheep, i did find the tracks but they were nonsensical. For example, one line of tracks i found was going N, then empty tiles until i find another line going SE, then repeat empty tiles until i found a couple of tracks going in circles. A little walk S reveals some more going W and so on and so forth until i end up around the original first tracks i found. Makes you wonder where the heck was this sheep going. In the end i tried the ritual on the tracks i found and it didn't work.
It kind of happens the same when you are actively hunting, some tracks will just give you outright mixed signals and you will end up losing the animal because of it. I wonder if they plan on expandind the tracking system, maybe add auditive clues of animals escaping or something? I'm no hunter so no idea how it actually works, but as i see it the tracks as they are really fall short for the "stalking" they intend you to do on animals when you hunt for them.