As a DM, I feel like I have a pretty solid grasp on how to build interesting combat and social encounters for parties of any level. However, I often struggle to do the same for the exploration pillar of the same, especially at mid to high levels.
Note that this question is about the exploration pillar as described in the basic rules:
Exploration includes both the adventurers’ movement through the world and their interaction with objects and situations that require their attention. Exploration is the give-and-take of the players describing what they want their characters to do, and the Dungeon Master telling the players what happens as a result. On a large scale, that might involve the characters spending a day crossing a rolling plain or an hour making their way through caverns underground. On the smallest scale, it could mean one character pulling a lever in a dungeon room to see what happens.
The problem that I'm facing is that most exploration challenges I can think of such as deep chasms, poisonous swamps, lava streams, hidden treasures, et cetera that are suitable for low-level (tier 1) characters, are trivially defeated once the party has access to spells such as levitate, fly, locate object, create food and water, etc. Some of these spells are available at lower levels but there they actually take a significant investment of spell slots, which becomes less of an issue at higher levels.
I do not want to take away these spells from the party, but that means many exploration challenges I put on fail to provide an actual challenge.
I would like to build exploration challenges that are appropriate for characters of mid (tier 2) and high (tier 3 and 4) levels. For combat challenges this is easy to do by using creatures of a higher CR, and likewise for social challenges the party can move from dealing with local lords and hedge mages to dealing with kings and archmages. So my question is: how do I scale up an exploration challenge to higher levels so that they are not trivially defeated?