I mean stepping out of the math constraints of encounter design vs. level that 4e suggests... something many advocates of 4e say can and should be done by the DM if he wants to since they are just guidelines and not rules.
I don't quite get this. Who advocates that the level-relative numbers for 4e - damage, defences, DCs, etc - should be ignored?
A monster that can do 150 damage as spike damage vs all targets is attacking (let's say) with 6d12+80, or an average of 119, which even allowing for double normal damage for some sort of uber encounter power is still appropriate to a monster of level 50 or so (on the MM3 level +8 as base damage model). I don't think I've ever seen anyone suggest that level 50 monsters (or hazards, in this case) will work well as combatants for level 13 PCs.
I don't really know what you think 4e's encounter-building guidelines are for, but I have a pretty solid view myself: they are basically saying "Use these numbers - these defences, these damage numbers, these skill DCs - and you will get a nicely paced, satisfying play experience". That's why the general advice is - if you have a bigger or smaller party, or want to make a fighter more challenging, you're better off changing the number of opponents (or turning some into elites or solos, or decomposing elites or solos downwards for small groups) than levelling up and down, as too big a level disparity will produce unsatisfying play results even if the odds remain somewhat comparable.
You may call this "player entitlement" (to what? a fun game? doesn't sound so bad to me!); I think that it creates a sort of confidence in the players that they can narrate their PCs' wacky plans without worrying that the GM will set a hosing DC or impose hosing damage as a consequence.
I hope this also makes it clear that I think the level-appropriate DC numbers, defences, attack bonuses, damage numbers etc are more important - a lot more important - than the encounter-XP numbers. Once into mid-heroic, and certainly into paragon, a party should be able to handle an encounter several levels above its own without too much trouble, at least once or twice a day; but that flexibility around encounter XP budgets is pretty orthogonal to the question of "How much damage should my monsters be doing, with what bonus to hit?"
It is in this second domain that the OP describes a pretty bad GMing error. (@Neonchameleon refers to foreshadowing - monsters with instakill abilities, like medusae, bodaks, etc, all have foreshadowing via both reputation with players and the monster knowledge mechanic. The GM, as described in the OP, does not seem to have done anything like that.)
I certainly don't think 4e's advice will always create the best D&D game for every group or even the best 4e game for every group or am I missing your point here? YMMV of course.
My point (and it's related to one that [MENTION=22779]Hussar[/MENTION] made upthread) is that, if you're not going to use the mechanical chassis of 4e, what are you doing ostensibly running that system? There's a large variety of systems out there, many of which are less maths heavy and have much more overt room for GM fiat. One of them would probably suit this GM better.
I mean, once you take away the framework of level-relative DCs, bonuses and damage what is left of 4e? The d20 array of stats and the basic idea of rolling a d20 and hoping to get a high number? You could get that with Swords and Wizardry!