Huge post. I’ll break it down.
I’d like to give some perpsective as a player instead of as a designer. I hope it’s useful, but nothing would be as helpful as actually seeing an example of a couple of rooms of yours. But first and foremost, be absolutely prepared that players will very much not notice some of your cues, and when it comes to navigation, they may ignore them on purpose to explore elsewhere first. I can tell you I certainly do that, because by experience I know that, if the game wants me to go east, it means that the story is probably in that direction, and if I go that way I may not be able to come back and go west instead, thus missing out on the content that list west. As you may expect, it was scores of games with walking deads that pounded this behaviour into me, so if you wanna blame something, blame designs that allow for that.
Another thing is that it matters whether your audience is new to parser IF or accustomed to it. in fact, I’m assuming that you’re doing parser IF based on your post, but I suppose it might be choice-based too. Players who are an old hand at parser IF can still miss cues, but are more likely to explore everything more thoroughly, room-connections-wise if nothing else. Players who are not, and are therefore less at ease with the cardinal exits and how they map onto a 2d grid, less so. So if you specifically want non-regular-IFers to not be frustrated, you may have to meet them halfway.
I just thought of something that I’ve seen some games do. When they list exits - either in the room description or in the status bar or both - they sometimes CAPITALISE, or bolden, room exits which you haven’t explored yet. This may be a real boon to your players. Alternatively, and this doesn’t work for every game/engine but it works for some, you can consider a small side window where you list the available exits in the layout of a cardinal rose as they are available. If N/E/S are the available exits, you get NORTH at the top, EAST lower and to the right, SOUTH centered at to the bottom.
If you find your players are missing navigation cues that you really want to nudge them towards, these are things you can do.
Everything I am about to say is subjective and relates to my personal experience and thoughts on design.
“instead of just moving north, south, east, and west without thinking.”
I find that in choice-based IF it’s really easy to fall into the situation where you’re choosing options without thinking, but in parser-IF that can be really hard. Especially if you’re navigating. Navigating, to me, usually becomes mindless only where there’s a bunch of rooms in a row with nothing but barely-interactive fluff. I’m like, “ok, I get the mood-setting, now where do I go to advance the story or to find more meaningful interaction?”
Is your game primarily a walking simulator? If so, the player should be primed towards that so that they don’t expect interactivity and explicit goals, and learn that the journey is the point. The Fire Tower is worth a look for anyone interested in doind thing.
“Right now, I describe things like a creek, a fallen tree, a hill, and an old cabin so players can figure out where they are.”
That is excellent. You actively want the player not to get confused and/or lost and/or turned around. It’s important to keep the player aware of where they are.
“The problem is that a couple of people who tried it completely missed those details. They wandered around until they got frustrated, even though I thought the clues were pretty noticeable.”
That could be you but it could also be them. Again, don’t underestimate the player’s ability to not do what you want. That’s what players do.
In IF design, you are not so much setting a path for the player to follow, as putting walls everywhere you don’t want them to go. Players are a lot more like cats than sheep. Try herding either.
The first thing I’d like to do is see that description, because it could be that the details of the landmarks just get lost in the noise.
I don’t quite understand what it is it that your players are doing. Are they completely overlooking exits? Or are they supposed to travel to certain landmarks in certain order? Is your map arranged in the usual 2d-grip map format? Normally, navigation-wise, a player wouldn’t get frustrated until they’ve at least been to every room that’s accessible to them, unless they got confused by the map and/or genuinely completely missed that a certain exit exists.
If every player is missing your cues for one specific exit, that’s a pretty big tell that you could probably do something about that, but players missing cues and having to pick them up later, in general, is par for the course. Players being frustrated over that is probably unavoidable… but minimisable, if you want, by using those tricks I mentioned in the beginning. Or you can, at intervals, drop lines that will slightly focus your attention on the landmarks. “As the sun passes behind a cloud and it gets rather chilly, you wish, for a moment, you were in that cabin. But the sun soon comes out again, and all is pleasantly warm”, or something.
“If I start repeating every important landmark, I’m worried the puzzle will become too easy. On the other hand, if I leave everything as it is, some players might think the navigation is just random.”
Basically, you’re asking “How much clueing does my navigation puzzle need?” That’s the question in puzzle design. 
No easy answers, I’m afraid. But I hope I’ve given you some things to think about.
“It just got me thinking about how people naturally use landmarks together with a sense of direction, and whether that feeling can be recreated with good writing alone.”
If you’re interested in that, you may definitely want to check out Blue Lacuna. My personal experience (and I can’t stress that enouogh) is that the NSEW convention is easily mapped into a 2d grid, and that makes it really easy to navigate and position myself spatially. Every navigation system that messes with that turns navigation into a bulkier, slower experience (including nautical directions). My expectations of navigation is that it’s a tool that I use all the time, so it has to be fast, ready, accessible. I don’t want to think about the directions themselves; I want to think where I want to go. Then, I just go there. Now, I’ve been playing IF for so long I honestly have no idea whether I ever struggled with the cardinal directions. I think that my first real experience was with “Zork” in a collection that had all zork games up until Zork Nemesis, and they came with maps, and I was somewhat new to IF, so I thought you were supposed to play it with maps. The result is that cardinal directions with the map made it really really clear for me.
So you can also be very upfront about encouraging the player to map the game. Most games leave it up to the player, some explicitly encourage it. It’s harder to miss stuff when you’re mapping it on the side. You could also make an automap of your own, but I suspect that’d ruin your puzzle.
Long story short on this topic, games like Blue Lacuna which use (or can use) landmarks as opposed to cardinal directions, are more likely to confuse me and lose me and make me miss exits. And crucially, it’ll be harder for me to know where to go in order to return to a certain location.
“It just got me thinking about how people naturally use landmarks together with a sense of direction, and whether that feeling can be recreated with good writing alone.”
You are thinking along interesting lines, but bear in mind that IF is interactive. The reader doesn’t even read IF the same way as static fiction; for one thing, the player is more attuned to picking out stuff that they can interact with from the text. And mentally mapping out the game. The static reader often just enjoys it one line to the next; the player has to work with what you’re giving them. “Good writing” for a reader isn’t necessarily the same as “good writing” for a player.
The basic concept of “providing landmarks for easier orientation” is definitely, on paper, a good one. I’m not sure how exactly that works out for you in practice, or how you’re doing it, but the basic idea is sound.
“For those of you who have written exploration-heavy IF, how do you make players notice important navigation clues without making the text feel repetitive?”
Again, and as ever, speaking as a player. This has a lot to do with personal style and how badly you want to steer the players toward something. A player who is stuck will naturally walk around revisiting locations and looking more closely at stuff, so there’s stuff they will eventually pick up before long. I would be really interested in knowing the particular details of what got yuor players frustrated, because frustration means they got to the “stuck” part and walking around and revisiting old locations didn’t help. Since your puzzle is navigation, I am curious about what they missed.
“Do you deliberately repeat landmarks in different ways, or do you only mention them once and expect players to remember?”
That sounds like a stylistic decision as well. “Expecting players to remember” can backfire, so careful with that. But as long as the landmark is visible on the room description, I’d say you’d be fine. Just be careful with any text that may appear once and never again. Information useful to the player would ideally be reachable again, not shown once then gone. Oldschool design sensibilities were more along the lines of “I showed the player this clue once, if they weren’t paying attention, tough”. I don’t subscribe to that, because I think that is a game that doesn’t want to be solved. I want to work with a game in the process of solving it; a communication back-and-forth, lots of feedback. A game that may not handhold, may not spell it out, but is more interested in seeing me succeed that seeing me flail. Even if I have to work for it. And, again, a game that chooses to only show critical information once in a context where it could reasonably make the information available again (this is a very important qualifier) feels, to me, so unfriendly that I’m more likely to quit than to continue.
“Would you let players examine a location again to get a more detailed description, or is that giving away too much?
Absolutely let them examine a location again. This is directly related to what I just said. Don’t handicap the player for no good reason. Or do you mean that on subsequent examinations it reveals more? Careful with that, becase that teaches the player that “examining more than once may give different results”. Then you have players mechanically examining everything five times just to be sure, and very likely skimming (rather than reading) the result of the first couple of “examines”. So I wouldn’t advise that.
“Also, how do you handle situations where the player realizes they’re going in circles?“
The trouble is, how do you, the author, or the game, recognise the player is doing that? They may just be walking around thinking about stuff. They aren’t necessarily stuck. I dislike games that try to recognise when I’m lost when I’m just following my usual IF-playing, puzzle-solving process, which is meandering and can be frustrating for an outsider to see. I’m not sure I’d recommend you to try and capture the problem at this level. But if you do, I’d suggest gentle nudges, like the one I mentioned way up there about the sun and the cabin. If you start changing room descriptions like that, you risk really confusing the player.
“kept missing clues that seemed obvious while you were writing them.”
This is a very appropriate place to end: yeah, players will do that. That’s part of why IF is really unlike static fiction. This is not a passing problem you need to solve now, it’s something that is best incorporated into your general worldview as soon as possible. Players will miss your cues. And sometimes players will recognise the cues but intentionally do something else, because we experiment. We’re cats, rather than sheep. Heh, I suspect everyone who’s ever been a DM at an RPG session (I’ve never been in one personally) knows the feeling exactly.
Usually, for IF, I say to make the rooms, put the cues in there, let the players loose, and wait. Eventually, when they realise there’s nothing else to play with, they’ll come around to your cues.
If they do NOT… then think hard about what is going on. Maybe you’re giving them red herrings that they are following instead. Maybe they are not recognising your cues.
