What about having the map demand payment. It notices and informs the players about nearby secrets, but doesn't tell them where those secrets are for free.
"Hey, that's one huge chest of gold hidden away. What will you give me to help you find it?" The bigger and better the payment, the better their hints. Offer the map everything in the treasure chest and it will tell you exactly where to find it. However, it will magically teleport all the treasure away when you do find it.
Want to work it into the storyline even more, the map is an artifact created by a greedy devil. Deals are binding and payment is moved to a different dimension for collecting. Maybe later on this devil could become a foe using items and equipment the party gave up. Unfortunately for the devil, the map was made to only care about the collection of goods. It will tell the party anything they want if the price is right, including the owner's location.
The map can accept any form of payment, ale, money, items, sacrifices, slaves, ect. However good or evil they want to be. The more valuable or difficult for the party to give payment the more helpful the map is willing to be.