I have had much better luck with finding things that I see in the distance, many thanks to PALU. I don't use his method exactly, because I don't want to take for granted that I'm in the center of the tile when I zoom in. Instead I move around until I'm sure i'm in one of the corners, and proceed to walk the entire perimeter. This is much easier if the tile in question is bordered by different biomed tiles, but even if it's a sea of coniferous forest it's still doable. I'll often add a marker to the search tile with a big red X that way when I zoom out I can see if I've wandered too far. In my experiments the width and height of a tile is around 60 paces, but I rarely count each pace as I'm looking for tracks, I just have an idea of how much of a tile fits on my screen and keep it in mind as I move. If I'm ever not sure I'll zoom out and see if my dude is still on the X that I put on the map.
To Bedlam: I only started playing recently, but I've found the tracking skill to be incredibly handy in difficult tracking situations where the fresh tracks I'm interested in are all mixed up with half a dozen other animal tracks spread out over a two week period. True you can use it to identify tracks that you can already see on the screen, but it can also make new tracks appear that your character didn't notice before. For instance, if I see very fresh stag tracks leading northeast, but I don't see the next set of tracks, I'll use my tracking skill on that spot and quite often my character will discover that next set of tracks that wasn't visible before. Once he does discover them, they will magically appear on the screen so you can see them too. If I'm dealing with a numerous and mixed tracks situation and I can't figure out which way the bugger went, I'll hit "x' on the keyboard to examine each tile surrounding the last known tile the prey passed through, this will automatically use the tracking skill on each of those tiles without having to actually move there, and will frequently uncover tracks that weren't visible before. This does not count as using a turn in the game, so you don't lose time walking back and forth while the prey gets further away. This little trick is what took tracking to a whole new level for me.