Sorry for late reply. (Thanks to dck for in-depth reply.)
First, a disclaimer: I am hopelessly biased on this topic, because (1) labyrinths were the blueprint when I suggested portal vaults, (2) labyrinths are both the mythical source for minotaurs and also Crawl's source for this monster-equivalent of a player species, (3) I always liked to solve mazes. This is why I much rather think about how to improve labyrinths than support outright removal.
Second, a reassessment: the main advantages of timed portal vaults (besides the minor ones of: sources of theme; portal race choices and general niftiness, especially relevant in the early game) are that you only have attempt, cannot prepare very much and that the portal vault can change some rules.
Labyrinths change game rules but not very efficiently. As a theoretical exercise, would a 10x10 room be interesting where you enter and face the minotaur right away? I'd think so, assuming that the portal comes up early enough (something we have under control) -- i.e. the minotaur should be a very strong (possibly OOD) enemy by the time you meet him. Your task is assessing whether you can beef up yourself enough for that single fight.
The current labyrinth is just like this, only that you have the prefix of running through the maze. I think this is where most consternation comes from. So the real question if running through mazes can be made more interesting.
If not, we could just make labyrinths really small vaults. For flavour, there'd be a thin layer of maze-y structures, but you'd get to the minotaur right away. With this, we'd keep the source of a player monster and the tactical challenge would be preserved. In my opinion, this is a fallback position we always have at our disposal.
Now some ideas before such measures:
- I don't think that starvation is an interesting death, even if it happens very rarely. Therefore I suggest that you're just dispelled as soon as you hit the starving status (don't worry, a thematic reason for this can be found).
- With that out of the way, we can be more drastic about having the player pay with food. E.g. increased hunger (disabling sustenance if we want), and sending more hungry ghosts and harpies at the player.
- These monsters emanate from the minotaur and get to you using the shortest path (i.e. they don't wander around in the maze, they hunt you). The minotaur could be one of them (he, or a replacement, will be at the lair once you get there). We can be nice and mark the floor squares of the last ten or so steps these monsters took -- this way you get clues about how to get to the minotaur.
- The minotaur could get stronger the more minions he sends out. (For example, have a chance to be awake, pick up loot items, "find" a monster-usable potion.)
I believe that there is some (not too much) skill in doing these mazes. However, you can use resources to speed it up (so far digging & disintegration; if we replace some walls with lava, there would be flight; another option are pre-detected strong mimics: you cannot harm them from afar and they'll fight if you come near, but if you kill them, there's a hole in the wall).
Making the maze more of a race (I've tried to hint at how this could be done) has the effect that manual movement is definitely better than autoexplore. In other words, there would now be a gameplay reason to disable autoexplore, rather than "we don't want you to get to the battle at the push of a button and the expense of half a ration". You want to be quick, and autoexplore cannot decide for you if you want to use digging/disintegration or take on this mimic.
Final disclaimer: I don't really expect to convince hardened labyrinth-haters by this. I am just thinking about ways which might make me enjoy labyrinths more (and as I said, I already enjoy going through them -- it never takes me long, but I admit they don't pose decisions before the battle).
By the way, more vaults are always good. They make it easier to navigate the maze (for mnemonic and for layout reasons) but I'd advise against many loot-heavy vaults. We don't want to encourage players to fully explore labyrinths: they are supposed to find the minotaur and fight him.