If you're on a bike or in a car, you can often home in on pokemon based on them appearing and disappearing on the nearby list, along with some knowledge of areas where pokemon tend to spawn. My SO and I have caught a couple of rare ones like this (one person drives, and the other operates both phones).

But I agree completely that it's more fun when you have a map or the long lost footprints to be able to zero in on foot.