Hello. I am a relatively new/bad player so sorry if the following post seems stupid.
I agree with dpeg that having exploration challenges as well as combat and character building challenges would be really nice. It's a part of the game that is largely automated (not that that is a bad thing). This is why I can appreciate and like on some level that the Labyrinth exists. However, as said before, it is also fairly easy and is abit boring to pass through. It is not optional the same way that selling things to the shop is not optional (should it be implemented); it gives you loot essentially for free (with a little food cost) and skipping it would be intentionally shooting yourself in the foot, forcing you if you wanted to play optimally to always do it. It becomes a decent reward for very little risk and involvement.
However, I feel that shifting the focus of the labyrinth to involve more monsters would lose "the point" of the labyrinth, having an exploration-based challenge. When I personally think exploration-challenge, I think either 1) Stealth Runs or 2) Speed Runs or 3) Both. To this end, I would like to offer some ideas that, while they might need tweaking, might be helpful in keeping that feel. For these, I assume the creation of a much tougher monster than the basic minotaur which I call the LabMinotaur.
1) Have multiple paths leading to the central loot hub. Of these paths, have 1/3 with visible but dangerous mechanical traps, 1/3 with sleeping monsters with status effects (for example ugly things) or zot traps and 1/3 with a clear but winding path with a hungry ghost. This way, you have a choice between avoiding combat but taking your chances with traps or dealing with a slow and status-effected death while avoiding the traps, both of which can be subverted by trying to find a path that actually a) is clear of enemies and traps and b) gets you closer to your goal but needs you to keep trying to find a fast way to get to the centre. Map rot should be decreased/removed. Dead ends are probably not preferred, rather several paths lead to the centre or loop back around, theyre just all dangerous in some way.
2) Make the Labyrinth as small as the Ossuary. but more "cramped". LoS is reduced (my idea was to 3 squares but this might be too drastic). At 50% of the intersections, there is "crunchy glass" covering the branching points of the intersection. Stepping on the glass alerts the LabMinotaur, who is awake and can triangulate your position with some effort. Similarly, the LabMinotaur who is normally hidden, reveals his direction and distance whenever he steps on the crunchy glass. No map rot. You are aware of your starting point in relation to the maze when you enter. (preferably always at a corner) with the loot always in the center. In this case, the LabMinotaur is meant to find you and kill you as opposed to being a guardian. Alarm traps don't work for giving the location. Noise scrolls could be handy decoys as an aside.
3) The Labyrinth is actually a trick maze, like The Lost Woods in Legend of Zelda and has no real way to get to the center unless you find the relevant key, pressure plate, trick to getting in, which are in vaults. The vaults can be tracked similar to caravans and things, "You hear the sound of a key jangling nearby." The vaults can have combat.
4) Instead of making it a hunt to find the loot/minotaur/exit, make it a chase. To expand on what some have suggested earlier, instead of giving the player the trail of breadcrumbs, give it to the minotaur and have him start about 10 squares in front of you or something. The minotaur is decked out in all the gear and loot and you have to kill him to get it off of him. On that note, the minotaur tries to reach a pre-determined point on the map that is incredibly hard to break into (water, single corridor for him to shoot you as you approach him, mechanical traps) that also has the exit. Your aim is to follow the minotaur, using his trail and take detours from the main path in an attempt to cut him off before he gets to this point because if he does so, he can just camp and wait for you to show up. For example, he starts off with the melee loot and the ranged weapon loot spawns inside his bastion.
These are four different ideas that hopefully show how movement and careful exploration can still be a theme for the Labyrinth, at least as I could see it happening. I feel that if you try and solve the Labyrinth problem by just throwing in more monsters, there is no real differentiation between this and the normal dungeon apart from the corridors.
I don't know how hard they will be to implement, they're mostly just to give a take on it and some justification to the idea that exploration can still be a thing around which the portal can be based. I'm particularly biased towards (2). It feels like the most urgent and the trickiest of them.
Also, I'm sensing I'll be quoted on badwiki for this. Just make it a good one.
Saturday, 5th May 2012, 17:59 
