Soo... that's a yes to my "are your group trapped in 3e" then. If the rest of the group have your attitude, then you should probably ignore the entire skill challenge system and just go back to flat rolls, because it seems like you're not even willing to try to make it work.
Trapped in 3e? No. Being reasonable? Yes. And if you look at the 4e example Skill Challenges in the DMG, they also make choices that certain skills will not work (there's an example of a low-level challenge where Intimidate automatically generates a failure, even if you roll a 50).
Your example for instance - if the DM hasn't planned out the cell in detail, then "I use history and rolled high, and now I know about fact X that the DM hadn't previously thought about" doesn't seem silly to me at all: much like if I write up my character's background as "he's just a normal guy", the DM can feel free to invent family members, a hometown etc. And if he HAS planned it out in detail, then he should know it's history and be able to choose something relevant (or know for a fact that there is nothing relevant, which might be a useful fact in and of itself).
It of course depends on whether the GM has planned out the room more carefully. I chose an example that someone actually used in a pre-4e discussion thread. They argued vehemently that History should make a hole in the room even if the GM
had pre-planned the room in detail without the hole. This is ludicrous to me. And this isn't a 3e/4e thing. The 4e DMG specifically indicates that sketchy skill uses that don't really fit should be automatic failures, result in penalties to later rolls, or have extremely high DCs. I have every indication from the 4e DMG that 4e is approaching this in a reasonable fashion.
Agreed - that particular use IS insight. Why did she assume that the fine details of his clothing and equipment were irrelevant however? They're going to be a indicator of his treatment and conditions within the cult, or possibly give clues as to where they do their shopping. Either could make for possible bonus to diplomacy, intimidate, insight or bluff if used correctly.
The GM agreed that we could get clues to this information with Perception. But we had specified what we wanted to learn ahead of time (he asked us to state it before setting up the challenge), and those things were not among them.
I agree that in some cases, there are more skills that could help than in others. In our case, we knew already where the cult was based, etc. We just wanted to know about the identity and abilities of the higher-ranked members and their end goal. Perception would not have helped with that (a good example of where it might have helped was if the cultist had a hidden object on him with a symbol of Orcus and we didn't know it was a cult of Orcus or something, but we knew, and he didn't). This is from KotS, which seemed to have pretty detailed information of what this guy had and knew.
None of this is supposed to be a judgement of you and your group - there is no badwrongfun. It does seem that you're trying to argue that it's the numbers that destroy skill challenges, though, and to me that doesn't seem to be the case for your group.
It is indeed the numbers--some skills do not have a place in some skill challenges (or if they do, they have a place as defined by the DMG as auto-failures, penalties to later rolls, or exceedingly high DCs). The GM was doing us a kindness by telling us this ahead of time for each suggested skill use (since we weren't veterans of skill challenges and were trying to feel it out) rather than just letting us roll and then failing.