So, Beedo had a nice post about plot hooks in a "sandbox" style campaign, and over at The Tao of D&D the author wrote a great post about providing opportunities but not solutions.
This leads me to something I tell my players all the time - that my job as a GM is to present problems.
Their job is to solve them. When I make them I don't always even know if there is a solution.
I think the main danger of railroading is not "you have to deal with this, you have no choice" but rather "you have to deal with this, and figure out the solution I like or you get punished."
One is an adventure, the other is a test right out of high school. Does a lack of choice of adventures really matter so much if you can choose how to solve them? And conversely, does a plethora of adventure choices matter if the GM has a firm idea of the way you "should" solve them?
Now, all problems should potentially have some kind of solution. A Death Star trash compactor with no way to communicate out and no shutoff switch isn't fun, it's meanness straight out of (the best of?) the Grimtooth's Traps series. But you don't have to decide how they'd escape.
In a game with a repeating location - such as a megadungeon - you can leave that problem around until they are powerful and versatile enough to make a solution that works.
This is doubly true if you're defining things as you go. If the trap is a trash compactor type and a player says "We swim out the way the critter ducked out!" than, well, why not allow them to try? It's a cool solution. But don't cut off a solution that you pre-planned. If you provided an escape hatch, don't put bars across it that weren't there when you wrote it just to make the trap last longer. Don't have the Baron say no to their cunning plan just because you liked another cunning plan they discussed (out of his earshot, or even out of character) and then rejected.
The danger, to me, is planning the solution ahead of time. Then you get all pissed off when Alexander comes along with his sword and says "Here is what I think of making skill rolls to untie that big-ass Gordian Knot" and rolls against Shortsword instead.
Your job is to present problems that can potentially be solved. The PCs are the ones who need to solve them.
If you keep that division of labor, and let everyone know that's how it works, I predict much rejoicing.