The locations you can see on the map are the locations of the pets in the current round. To catch a pet you have to predict where the pets could go next in the next round and place your catchers on these spots - not where the pet actually it at this time.
Maybe that was the problem. FAQ really helps here:
There are 3 types of locations on the map:
- Den - Heart of the Forest, Big Tree, Magic glade, Cave (requires Climbing Gear), Old Ruins (requires Climbing Gear), Island (requiresBoat)
- Watering Point - Waterfall, Creek
- Hunting area - Eastern Fields, Western Fields, Big Field
Wild Pets visit them one by one. Every Wild pet has its Den. From the Den pets will move to the Watering Point and to the Hunting Area. If 2 pets go to the same location but there's a place only for one of them, they will fight and the loser will go back to the Den. You can place Observers to check the current position of the pets and then try to guess where the pets will go on the next turn.
Probably you will want to build Cartographers Guild if you want to focus on catching wild pets. This structure allows to see the current positions of wild pets. Please note that these positions will change on the next turn, although it's quite easy to predict where the pet will be on the next turn.