But what was the goal?
Is the goal to get the magic staff, specifically? If it is, its easy. They only need to find a portal or two to get to the Plane of Fire. In fact, as long as they can get to any of the elemental chaos, they can then walk to the Plane of Fire even if they start in the Plane of Water. Doesn't this require DM dependence? Well, yes. Because the DM needs to make sure they always have an avenue to accomplish their goal in a mundane fashion. Because otherwise, they're forcing the players to have a specific build or not advance at all.
What you're describing here is basically anathema to how I want to play a RPG - whether as player or, far more often, as GM.
You're in effect describing a cooperative story-telling game: the players start the story by describing how their PCs look for a portal (or whatever), then the GM takes up the story by telling them how they find it.
In classic D&D, spellcasting is not a version of this sort of play but an alternative to it. The player is permitted to actually establish the requisite element of the fiction (eg if using a plane shift spell, s/he can simply make it true, in the fiction, that there is a way for the PC(s) to get to the plane of fire).
There are other mechanical systems besides spells that can produce the same sort of play. 4e skill challenges are one example. Other examples are found in non-D&D RPGs.
All adventures need to have the answer to all their problems without needing anything in particular from a character, especially if that character plainly doesn't exist in the campaign to begin with. It makes no sense to ask a group without planar travel to go into a different plane and refuse them a way to get there.
I don't know where the idea of "asking a group to go into a different plane" comes from. The particular example I gave happened a couple of decades ago, so I don't remember all the details, but it was the players who wanted their PCs to go to the plane of fire. They (and their PCs) weren't being asked.
I find it easy to believe that the DM had naturally had a fire-based magic staff that the party needs located in the Plane of Fire. I also find it easy to believe that a plane-shift-capable character could make this journey easier.
What I find difficult to believe is that the DM had knowingly placed something the party needs to advance in a location where he knows there's only a few player-based ways to reach it while also refusing to place a single portal, NPC, or magic item that could allow them to reach it.
And here you seem to be envisaging a GM-driven railroad: the players
need their PCs to obtain the staff in order to "advance"; and the GM "places" a way to get it.
(There are versions of this that aren't railroads - ie puzzles, where the players
want their PCs to obtain the powerful widget; and the GM establishes a puzzle of some sort that must be solved in order to get the widget. Gygaxian dungeons have quite a bit of this. But in those cases the word "need" isn't apposite.)
I'm assuming a game where the
players decide what it is that their PCs want to do. And in some contexts this requires magic. Even in 4e - though as
@EzekielRaiden has pointed out, accessing magic in 4e is easier. I don't see this as objectionable in a fantasy RPG. As I posted upthread, I just find it strange to assert that there is no problem or goal that needs spellcasting to solve or attain it.