So I've made it to Level 5 of the Catacombs, and I can't seem to progress any further. All other avenues of the map are dead ends. Solid walls with no interactable objects/doors. As you can see in the image, there's explorable space beyond this area here, with a chest where my cursor is pointed. But there doesn't seem to be any means beyond this point. I'm a warrior with no magic investment, so I can't use a phasing scroll either.

I don't remember this ever happening way back in the day, though I could imagine it being a problem.

Yeah, I had finished the Valor quest prior to getting stuck actually. Wearing the armor you get from it in the screenshot.

Gave the entirety of the level a once over again, but still no dice. Thinking I might just have to start a new game to refresh the maps.

Town portal out, and then look for the opened tomb near the church. This will allow you to go back to level 5 that opens once you have visited that floor. Check to see if that will allow you to finish the level.

Unfortunately, the stairs leading down from Level 4 and the passage to Tristram are right next to each other in this instance (the screenshot just barely cuts off the second set of stairs).

I have one more idea, but it requires a lot of reloading the game. First you need to go to Adria, and save the game. Then keep reloading the game till she sells a scroll of Phasing. Then you can go back down to where you can't go, and make another save that way you can reload till you teleport into the area you haven't been. Note that if you don't have 25 magic you may need to equip something that will increase the magic stat.

Uhhhh...unfortunately, in my haste (and impatience), I started a new save to refresh the maps. It's only 5 levels down so I figured it would have been faster to just work my way down again rather than trying to resolve the issues.

Oops. That was reckless of me. I didn't realize we could have more thoroughly investigated to pinpoint the cause of the issue. But I swear the stairs were right next to each other. I went up and down the level 4 passage/Tristram shortcut multiple times in a vain attempt to fix the problem.

One thing I overlooked was the staff I got from Gharbad. I completely forgot that it gives you Phase charges with no magic stat required. I didn't identify it till the new game. Is it possible that the game generates maps on the assumption that you'll have the staff, and thus be able to teleport over walls? That seems...unlikely. Like I said in my first post, I don't remember anything like this ever happening, and some quick google searching to find similar problems yielded 0 results.

Anyway, I apologize for acting so quickly to just move on with the game rather than properly examining the issue.

The drop you get from Gharbad The Weak is completely random. I got a wooden club (that looks like a plank) with awful stats.

The stairs to a lower level can sometimes be in the same room as the stairs up. But the way it looks you just got a bad map seed because the levels are procedurally generated. That is very rare. If you explored the whole level and didn't find any way to get there it could be that the map generator did an oopsie.
Unless it was the area of the "Halls of the dead" which is a quest on a lower level (you enter the Halls of the Dead by going up a staircase on a later level.

No, the game shouldn't create maps with impassable walls. It's my first time seeing this too :)

The level generator code is know to have a buffer overflow in it that can cause malformed levels some times.