Pickles JG
First Post
I understand where you are coming from precisely and while not familiar with other versions can state my beliefs on why this occurs.
First. I too have a group of 5 and a group of 6.
Past the first few levels, attack rating caps out, as well as armor class. The only difference then is HP. This allows creatures of lower level to still have a good chance to hit higher level creatures. The down side is this doesn't make higher level creatures directly more challenging. This is due to killing an individual creature takes longer but not harder (unless they have resists/immunity).
I personally have 2 solutions for you.
1 - have additional low level creatures along with the solo creature. I know this is a "cop out" response, but it works.
2 - customize the HP of the creature to be even greater. - This will most likely achieve what you are looking for. This in D&D Next will allow you to make fights more challenging due to making the fights longer, but still possible. This is due to exactly what you say, if you throw a cloudkill Lich at the party, if they fail they pretty much die. They just don't have the HP yet.
3 - A combination of 1 and 2. This is how I have designed my high level content for the future. To have an insanely high HP level 20 boss, with a lot of low level support creatures.
So use the 4e solution?

Fights against solo monsters have always been pretty dull in any edition often resolving into with a bunch of players standing around the single monster bashing it. 4e did not help this in the early days with huge bags of HP & little threat & also great vulnerability to control effects.
This is the risk inherent in solution 2 & I find solution 1 well 3 probably works better.
Another solution is dynamic environments rather than dynamic enemy rosters. One of the good encounters in the H series had the PC spread-out in a trapped environment to perform a ritual. The ritual opened a portal for them to escape through (IIRC) & also released a Dragon. The dragon was too fat to die at all quickly to the PCs & had movement tricks to keep them spread out & push them into traps etc (I think it was green dragon mind control).
Other things like this damaging environments that can be avoided but the solo can make use of or summoning portals or whatever, lots of HP & some other threat or reason the fight does not just resolve into everyone standing around hacking.
Going to the original scenario - PCs ambushing a monster is often hugely beneficial - try it with the wyvern ambushing the PCs - fly in grab a PC & fly off with them at a slow pace as he's weighed down. The other PCs have to rush to keep up & will waste actions trying to do so. (or just fly a few hundred feet up drop repeat - probably not the most fun).
The attritional style of combats that seems to be favoured in this edition means that they are often anticlimactic - the par result is lose a few HP & the variance is often lose no HP or lose slightly more than a few.
If this encounter was some just a throw away encounter then that's an acceptable risk, don't sweat it - it is frustrating if it was supposed to be some end level boss battle climax though.