A few ideas, tried in the past, caused great frustration and some amusement with my players:

The twisting shifting maze
a network of tunnels, quite large in scale, that keep shifting and changing (i used underwater tunnels, also a creation of the Daelkyr, the underwater element added the necessity of time before water breathing magic failed). the tunnels shift, and confuse the senses so it is hard to navigate them. the only visible help is in the form of cryptic runes above exits and entrances, which the party may or may not figure out (knowledge abberation or decipher script may help, but it in the end this is a puzzle)

how does this work from the DMs chair:
- you plan a few "major" rooms that are sort of nexuses for the rest, about 6-10 should suffice.
- there should also be quite a feow other "generic/ minor" rooms that can be accessed. i suggest planning about 15-20, and possibly making more if needed.
- Moving from tunnel to tunnel is quite random, with some odds favoring certain types of rooms, but...
- Navigating the tunnels might require some skill (dungeoneering?) which may be aided by other skills, but should be quite difficult. Success enables adjusting the random die roll more towards a certain kind of room. A higher difficulty DC might enable returning to a better known room (Easier for major, less for minor)
- The runes over the exits change as the tunnels change, but they increase the odds for the specific rooms they suggest to. The runes over entrances may give a clue to the type of room you're about to enter (Major of some sort, monster den, empty, unnatural hazard, safe place and so on)
- Ultimately there should be some runes/ clues to direct to "deeper" rooms which hold slightly different, more dangerous challenges, (My Aboleth was here) before moving on...
- Very Important: This kind of challenge calls highly on the creativity of the players, and thinking originally. Allow for that.

Visions and Dreams
A bit similar to the previous idea, but different. The party finds itself in a sort of a dream/ vision/ scene, and as different characters. One or two of them truly believe they are these other persons, while the rest are themselves. However, the scene shatters (will be explained soon) if the make belief is unmade for the believing characters. The scenes should be weird, mad, perhaps vergin on insanity and improbability.
- Each scene has 2-3 ways of solving to "get out" to another scene. This is the equivalent of getting to another "room" of this maze.
- Every 2nd or 3rd such scene should have a way of "advancing upwards/ lower" to a different level of madness and insanity- more extreme scenes.
- if the make belief is shattered, the major characters(? the ones who believe) are confronted against their madness too much, the scene tears- all characters suffer some sort of mental damage (hp? wis damage?) and are randomly tossed to a different scene.
-you can pepper this "scene scape" with various monster or creatures feeding on the scenes like the different quori or psychic creatures, which just add to the crazy.
- all in all i had like 15 scenes, arranged in 3-4 "levels" (can't remember).
- works well ONLY for players who like a roleplaying challenge, people who'd like something like "who's line is it anyway- the crazy version". led to a lot of laughs with my party.
- I suggest you also put in some scenes from the party's past, the character's past before he party (distorted to make them seem otherwise), or of NPCs they came to know ("Is it real or not?")

A monster for a day
The party's flesh is shape shifted to the forms of difficult to play (but INTERESTING) monsters, in order to overcome their challenges. various low level abberations (Gibbering Mouther?), magical beasts, perhaps outsiders and the like. have fun with it, but prepare adjust character sheets in advance. I'll leave it to you to decide ho exactly this works, but I think the polymorph/ shape change spells are a way to start.
- picking the right monsters is crucial- they should provide a challenge to the character (both mechanically- how it works with class abilities, but also mentally and emotionally), But also be cool and itneresting enough to provide an interesting experience.
- If possible I'd suggest monster who's racial abilities offer solutions to problems other than just combat- sliding through halls, reading thoughs, and the like.
- be weary of how equipment works in the new forms- my suggestion is to have it melt to the new forms completely, let the players resolve being monsters...

I hope this helps.