I established the nether planes as non euclidean regions with screwed up geometry. You need good rolls in knowledge -the planes - to navigate it.
What i did in practice was putting 20 locations at random in a map. Some of them were notable, for example they had cities and people to interact with, or they had specific geo effect. Then i put them on a list, numbered.
The players started from 1, and they had to reach 20. The players did not know the numbers, or how it was arranged. The rules were
- a dc 25 would get them to the next number. The players studied for this, and i decided they could do this authomatically.
- a dc 30 would let them advance two or three numbers.
- a dc 40 on a prime number would let them go forward a lot (don't remember exact rules)
- if they failed a check, they got lost and returned to 1
- at every "step" there was a random encounter. They could avoid them with hide or survival, but the dc kept getting higher for every skipped encounter; would reset on actual fights.

So the challenge was getting to 20 without failing rolls or getting too much attrition.
It took the players many sessions to figure out the code. In the end, they cut the knot: they interacted enough with fiends that they managed to hire a guide.