1. There only has to be one ultimate clue in one location, but you could have more than one if you wanted. :|a There should definitely be smaller clues in various locations, though.
2. They don't have to be in every zone, but they should be easy to run into and encounter, to give the players a chance to convince them to give up on their perfect place.