I noticed this too. It could be a bug in the game that causes the GPS to be inaccurate with the paw prints. A Growlithe showed up near me, allowing me to capture it, but my grid says 3 paw prints for all the 9 Pokemon, even with the white pokeball loading symbol gone (done loading). Also, grass/leaf patches don't always mean there is a Pokemon. I ran far to a rustling patch before, but all the Pokemon on my grid were 3 paws away. More info on rustling leaves
Although I believe this is an unintentional bug by Niantic, I would recommend searching primarily for just 2 and 1 paw print Pokemon if it shows up. The 3 paw prints seem buggy, even though it means 150 meters to 200 meters within range according to this answer: Step Distance
Try to go with a group a friends so that you cover more area and find Pokemon more easily. In addition, you can try going toward leaf patches for a slightly higher chance of an encounter.
EDIT: As of now, I have iPhone 6s with version 1.0.2 in the app store of Pokemon Go. The in-game version says 0.29.2
Source: My experience