This actually makes the spell even better in some ways because if you can get the rogue to sneak into a spot and hide a (permanently invisible?) key there, you can teleport in: vs. having to have the cleric stomp around to that place in person. But at least it sets a physical object dependency vs. just having to have been to a place any time in your life, and in theory someone could take the key and throw it into the ocean or some place that makes casting the spell very bad, lol.
Thank you all for these thoughts though, I love all these ideas!