Right on Castellan! You hit almost every major point, however, there are a few details missing punkorange. How many players do you usually run and what is the adjust EL vs CR ratio. By the rules, if you are running a four person party of equivilant level into monster EQUAL to their CR/EL then in 14 encounters they will level up, that means that they will be using a fair amount of their available resources on every encounter.
If the party is heavy in one area versus another that will swing the balance one way or another too; for example, a heavily magic using party will exhaust most of their 'available power' with just a couple of encounters as they all try to stand back and blast away with magic, especially at the lowere levels when magic-using characters have very little in the way of multiple spells per day. On the other hand a party of just clerics at lower levels could easily go after monsters outside of their CR range and keep on going, as each one drops back and buffs the others or heals to keep them in the fight. Never using all of their magic and each one fighting as effectively as a low-level fighter (for the most part).
For the party's part, they have to remember that
this isn't a video game, there are no save points and character death really does happen. If the group you run is made up of rather young players (born after '80), I doubt any of you would remember the days of the 'killer dungeon' when you EXPECTED your character to be killed, sometimes before you ever got to the dungeon. If you are older, (born before '72) tell them to suck it up or you'll pull out a copy of 'Tomb of Horrors' and remind them of the bad old days.
As for your part, do a very critical and unbiased evaluation of the encounters they have had versus the 'relative power' of the party. If their fate is due to poor dice rolls, hey that's fate and it happens, if it is due to your specific choice of encounters to counter their strong points,
you need to make some serious decision about your DMing style. Without getting into psycho-analyzing your play style and just stating as a general rule;
Remember you are not at odds with the players and you are not playing against them, you are in a partnership to challenge them in a setting of fantastic design. It is meant to be both fun and memorable for both parties involved. I speak this general warning in most of these 'what am I doing wrong?" posts, because I wore the 'me versus them cap' for a long time before I figured out what I was doing wrong.
In conclusion, evaluate them, and evaluate yourself. If it is truly their problem, then speak to them, through NPCs or out of game if need be, and then following the advice from Castellan by hitting them with the random encounters to get them to change. If it is a failure on your part, make the adjustments to help them have a great time, but never let them off the hook entirely, remember that dungeoneering is dangerous work and casualties and character death is just a part of life.
Hope this helps
TF.