The point of my idea is that the game is just as much fun if they miss or succeed, because they can still find the things just with a different story.
Every roll they succeed with gives a sense of success, every roll they fail opens new opportunities to find the stuff in a different way. And the perception rolls do make a difference, but by succes/other opportunity instead of success/failure.