There are several themes running throughout this thread. They appear to be:
1) Ensure that the trap exists in logical circumstances. The inhabitants (if any) must be able to avoid them in their day to day existence. The exception being hastily constructed traps, put in place because the inhabitants know there are intruders.
2) Give the players a precedent. The presence of traps needs to be foreshadowed in some manner.
Once those criteria are satisfied, practically anything is fair game.
I think that's a fair summary.
This might fall into #2, but I think you can add a third point.
3) Regardless of how dastardly, cunning, or tricky, the villain always has a sense of fairplay.
That is to say, the villain believes in giving his victims a fair chance to bypass his tricks. The villain has some set of simple rules by which all traps are constructed. In Acerak's case, in constructing the 'Tomb of Horrors' one of his rules is, "The hero should always act like a hero. Unheroic (greedy) acts will always be punished. Heroic (brave, sacrificial) acts, will be rewarded." Another one of his rules is that devil's heads have a consistant meaning. Even though arguably the goal of the villain should be to frustrate the player's by leaving false clues, by randomly making some situations true to their appearances and others not, by creating traps for which there is no true solution (darned if you do, damned if you don't), and so forth this should never actually happen,
because its not the goal of the DM to frustrate or defeat the players. The goal of the DM is to present the player's with a challenging but solvable puzzle, so that when the player's do begin to succeed they obtain a great satisfaction in doing so (because its not easy and takes some skill, insight, and planning), and conversely that when they fail they feel that they should have seen it coming.
So for example, someone mentioned a grimtooth trap where the pit was false and the apparant area of safety was a trap. I would only consider that a fair and interesting trap if it it set a theme for the entire dungeon of "fair is foul, and foul is fair". That is, the players should eventually grasp that the rule of this dungeon is that everything is backwards - that warning signs mean safety and signs of safety mean death; that evil portents mean security, but beautiful trappings mean a horrible fate await. And, that armed with this insight, the players should be able to consistantly beat the puzzles presented by the dungeon.
If you are going to deviate from the rules, then you can only do so in a climatic fashion. In the case of the 'fair is foul and foul is fair' dungeon, the very last room where the villain slumbers in his sarcophagus can the twist that fair really is fair and foul really is foul, but no dramatically speaking it can't occur anywhere else (and should have foreshadowing to boot). Remember, a dungeon is a story, the rooms are episode and the path through the dungeon represents the different ways the episodes can be arranged. Your map is your plot. In the 'fair is foul and foul is fair' dungeon we are building on the stories theme, and the twist - the epiphany - can only occur at the climatic point.
Think about the 'Harry Potter' series. In each of the first 5 books, there is a twist. And, to a very large extent, it is the same twist in every book. In the 6th book, at the climax the twist is - there is no twist. That only works in a dramatic fashion if we've very carefully built up our theme in the previous episodes of the story.