As far as everyone knows, the Maze has always been there; the strange pair of gates set in the side of a mountain a common feature in every painting of the area, no matter how ancient. One white, one red, nobody knows what they're made of but they resist any attempt to damage them; they’re always slightly cool to the touch no matter the weather, they have a very reflective surface, and if you look at them in a bright light, sometimes it looks as if they glow on their own.
The important thing is what’s on the other side of them, of course. The Maze itself is a strange place where the normal rules are suspended, and its own set takes their place. It’s a place filled with puzzles and riddles, monsters and traps; it’s always consistent with itself in any single run but is never the same two times around, and sometimes you could swear it has a sadistic streak, delighting in tricking the unwary adventurer.
It is a dangerous place, as so many people will rush to tell you; most people who go in never come out, and even those who do usually end up scarred for life. They also bring out with them enormous piles of riches, which is why people keep going in anyway.
In a room the PCs find a decomposing body half in and half out of a mirror, the result of an attemp to create a [Mirror Golem] that went horribly wrong.
A typical iron ore mine, the Irongate was closed some years ago and the entrance was closed off with a heavy gate of oak and thick iron bands, the Irongate. The mine itself was abandoned because it was a breeding ground for dire rats and many of the miners suffered from giant rodent bites as well as diseases from said bites. The mines are haunted by the ghosts of the men who died in dire rat swarms, adding to the mine's unpleasant character.
The PCs encounter an elaborate trap room, designed to fill with water, drowning those inside. Clever and resourceful, they disable the trap and move on.
Only later do they discover that this room is part of the elaborate cooling system that prevents beasts of elemental fire from overrunning the complex. While the fiery beasts run rampant, they begin setting fires, which causes the complex to become increasingly hot and smoke-filled. Additionally, the PCs now have to fight their way out past aggressive fire creatures...
The greatest tree in the woods has a secret, there is a dungeon under it made from the intricate web of roots. What creatures could reside here? What secrets will the PCs uncover?
What if you send the players in a dungeon that was already raided? Maybe you could have traps that are already set off, or the corpses of monsters etc.
A place where an architect has built a temple/shrine to an evil god inside the walls of another building, a castle or another place of importance.
Have a large room that elevates either up or down when triggering a trap. The floor can bring the players to new levels, where a mighty beast roams, or the floor flattens the players into the ceiling or drop into a pit of lava.
There are ruins, scattered about the world, and all are sealed with unbreakable locks.
When all of these locks suddenly open, what emerges?
A cave with weapons sunken into the walls, blades sticking out of the floor and ceiling, and so on. Possibly, any weapon used in it could be torn out of the hand and sink into the stone.
A large vertical cave has a constant, strong wind blowing out of it from the bowels of the earth. If one was to jump into the currents they would have a controlled ascent on the winds till they reached a height where their weight and the winds force reached equilibrium. Impossible to climb down naturally. What is it? Natural winds from the earth or a complex magical protection for an underground lair?
With regard to the plot "Sleeping Mines of Elathon":
You manage to get the water wheel in the mine working which operates a pump to clear the flooded lower levels. As you explore the dank tunnels of the lower galleries, you can hear the creaking of the wheel above. You enter a low-ceilinged passage and are crawling on your backs, when the creaking stops. The water starts seeping wetly around the back of your head...
Mining in a certain area turns all exposed skin (maybe just parts that are actively disturbing the chemicals that cause the reaction) of the those doing the mining to a dark blue color. Will wear off taking as many years/days spent in the mine.
The court wizards of Angolterre have been working for several generations to protect the dynasty. They see to it that the new monarch's names acronymically refer to a rune of protection. Once completed, the rune will make the dynasty almost invulnerable in battle, wise in counsel, etc. Unfortunately the next name, the only one that starts with the right letter, happens to have belonged to the worst monarch in living memory. Not much chance of getting the current ruler to name his child that, or for the people to put up with it if he did! What's a court wizard to do? The magic requires that the plot be kept secret of course...