What they need to do is make the 'hunting' system more 4th dimensional.

If you 'hear' a Pokemon near by (maybe you don't know what it is, just that you haven't seen it before), you also know a vague direction it's in; maybe not distance but direction.

That should stay on your map.

You move to a different location so you can triangulate it.

You hear it again and another slice lays on your map.

You investigate, but it's taken too long to get there. All you find are some footprints. (location saved to client device)

Later that day, or another day, the same noise is heard near that area, the client shows the pie slice again, but also loads the local markers within it.

You go to investigate the marker and see (maybe even capture) the Pokemon you'd been hunting.