Discussion with Brendan has started me thinking more about fairness issues. -C has covered the issue brilliantly with regard to traps. To put it simply: clues to traps should be given in description, players who listen carefully will be rewarded by not dying. But what about monsters? The threat level of a monster can be difficult to gauge - particularly if the DM uses a lot of unknown monsters. Also, I want to reward players who think - not necessarily those who know the game best. I think particularly in systems that heavily incentivize combat (e.g. Pathfinder) this is a serious problem. We want players to be wary of combat - but they have no other way to advance their characters (unless you dabble in the modern D&D devilry of a magic item commerce - a topic for another day). Therefore the players are inevitably going to take risks and fight unknown monsters. If we just let them die willy-nilly we will end up damaging fun. It may be fun at first to hurl characters at unknowable enemies, but its frustrating after many sessions of either starting new characters or not gaining experience.
CR: Ick. The WotC way is crappy and is not the game we wish to play.
Knowledge skills: the Pathfinder sort of fix. Roll and learn the monster's capabilities! Not only is this a horrendous example of a skill tax ("let's see, I'd better take knowledge-planes because no one has that yet") but it destroys the sense of exploring the unknown.
"So what if they are frustrated? They should learn to play better.": Not exactly swimming in grognards here. Plus, shouldn't the game be fun?
Scouting: My awesome solution. We need to provide clues and opportunities for the players to learn the capabilities of nasty monsters before they decide whether or not to fight them. The rust monster does not leave much intact metal around, ghouls leave a lot of gnawed on body parts around, you might be able to sneak up on the ogre encampment to determine their numbers, etc. As great as surprise is, players making intelligent decisions is better. If we can start them thinking in a scouting mode, then we can include real baddies, and start littering the dungeon floor with corpses of the foolish.