First don't start encounters by having them roll initiative. Present a monster as an obstacle in the way of their goal in the encounter. Their goal is "get through the maze of passages," but the umber hulks are only one reason the passages are hard. There are traps, the maze is hard to navigate, and so forth. If they're smart they will realize sneaking past the umber hulks will save them dailies and surges.
Second, make running away possible. In most editions of d&d including fourth, running away isn't really possible, and fighting through is usually easier than running away. Think about this, if you shift and run, you move 1 (shift) plus speed plus 2 (run) away, and grant CA. Your opponent can move and charge gaining +1 to hit from charging and CA because you ran. So to run away, there needs to be a house rule about it, or you need to give them wondrous items that help, like an ever-smoking bottle, or emergency teleport items, etc.
Third, give them easy encounters for crying out loud. If they're fighting on-level battles, and then encounter a level+4 solo brute, it is going to do twice as much damage than the last thing they fought. That first hit is going to shake them. "Did you say FORTY damage?" "Are you already bloodied?" "Bloodied? I'm almost DEAD."
Fourth, sounds like they're having a lot of fun. Keep from presenting the, with gates to the Balor's living room, and let them take on whatever they want. Remember this: hard enemies aren't necessarily higher level. The hardest enemies are proactive opponents who create time pressure situations. That dragon will be more dangerous when it burns a village every night. When the pcs come for the dragon, some villagers explain this. They explain that they think their village is next. That the dragon's Orc minions kill them if they leave the village, and his fire burns the village so there is no escape. They explain that they will give them 1000gp if they kill the dragon before nightfall. Oh, and it's already two in the afternoon, and dusk is at seven. The dragon cave is an hour away. That leaves four hours, no rest, countless orcs, and one badass dragon. Good luck doing all that in four hours without avoiding at least a few encounters.