Was thinking on this recently and was wondering about it mostly from the perspective of the 4e fans who claim that the encounter guidelines "work" in 4e. What does this mean? What is the criteria being used to determine this? Is a challenging encounter usually "challenging"? If so how do you relate this descriptor to what actually happens in an encounter? Same for easy and hard as well.
So, you're asking what is a challenging encounter, right? Really that depends on play style and is going to vary by group, even in 4e.
Overall, yes the 4e encounter building guidelines are a good starting point to allow the DM to predict roughly how difficult an encounter will be for a party of five PCs - how many resources the PCs will use, whether it is likely that a PC could die, the perceived tension of the players, etc.
However, once you start getting into larger/smaller parties, creative player use of rituals or high-level spells, start breaking the rules as a DM (eg. Lateral thinking encounters), include game-changing terrain powers or support, have alternate objectives besides "kill all monsters", and so forth, you quickly are in more advanced territory than a simple numbers game.
IME 4e encounter design has a good math basis, perhaps better than any previous edition's encounter building guidelines, but there is still very much an art to it.
On the other hand I would also be interested in hearing from those for which the guidelines don't work and why that is... In general is a hard encounter usually a cakewalk? Is challenging too easy? How do you view the descriptors of easy/challenging/hard and do 4e's encounter guidelines fall in line or outside of what you picture these descriptors as representing?
I'm running five 11th level PCs through a fight with a 15th level solo dragon designed as a 3-stage boss monster. This is a very hard encounter (L+4 or 5 is considered the upper limit of what PCs can handle). They've got it to the third stage, but their leader died, and they've depleted most of their resources (healing, action points, daily/encounter powers). While the players have some NPC minions, ballistae, and had 2 hours to prepare, the dragon is heavily customized, has a series of hazards associated with it, and I played the dragon as a wicked tactician.
We haven't finished the fight yet but it seems like an almost even match. I'd say the PCs have a 40-50% chance of defeating the dragon with more alive than dead/unconscious, depending on their tactics, dice rolls, and outside-of-the-box thinking. And maybe a 60-70% chance of defeating the dragon with 1 or 2 PCs left standing.
So not a cakewalk by any means.