At their level, it's what they can expect. They chose the wand of bull's strength over the wand of resist energy, after all.
In fact, fireball is not the worst thing you could have done to them, not by a long way, there are far worse things a wizard can unleash. Just remind them that anything they can do, the enemy can do.
The main thing I think you need to beware of is that when the party buffs up before a fight, like bonuses (except dodge and untyped bonuses) do not stack. If a character has a belt of strength and somebody casts bull's strength on them, they only get the highest bonus of the two as both are enhancement bonuses.
There will always be strengths and weaknesses in a party, and what seems like a horrible fight on paper might turn out to be a walk in the park. While a seemingly innocent random encounter can spell doom for the same group.
And some players just do the numbers game better than others. I had a party in my Kingmaker game (which is on indefinite hiatus) where I can pretty much send stuff that is 5-8 CR above their level, and expect them to survive just fine. In fact, most things that is only 1-4 levels above them I expect them to deal with without expending significant resources.
That said, the party IS supposed to win. Just expending reasonable resources and effort doing so, to make things interesting. You describe a party that spends what seems to me like a minor fortune on consumables, which makes the first 10-20 fights really easy... and then they are gone.
Also, you have a wizard and a paladin. The best caster and the best melee classes.
Spells that pretty much break the game at this level of play, if used well:
- Black Tentacles
- Slow
- Haste
- Confusion (if cast before battle is joined)
They are all in the "Must have" section of any wizard guide.
Also get some good defense spells for your mage in case the paladin actually gets to him. Things like:
- False Life and Greater False Life
- Mirror Image
- Invisibility
- Mage Armor & Shield (1st level but at this level, they probably will always have it on.
That plus the debuffs above will make life a living hell for the party. Add in a bruiser too that can take advantage of the debuffs above. Remember, never EVER do a final solo encounter type of boss unless you make him nigh-TPK worthy.
For the cleric, he's level 7 now and can learn 4th level spells. Watch out for:
- Sanctuary
- Terrible Remorse
- Silence
- Grace
- Freedom of Movement
- ***Blessing of Fervor***
Blessing of Fervor is a BIG spell to keep an eye out for. Here is what it does:
With this blessing, you call your allies to move forth and empower them to conquer and become victorious. Each round for the duration of this spell, each of your allies can choose one of the following bonuses for that round at the beginning of its turn (their choice).
* Increase its speed by 30 feet.
* Stand up as a swift action without provoking an attack of opportunity.
* Make one extra attack as part of a full attack action, using its highest base attack bonus.
* Gain a +2 bonus on attack rolls and a +2 dodge bonus to AC and Reflex saves.
* Cast a single spell of 2nd level or lower as if it were an enlarged, extended, silent, or still spell.These effects are not cumulative with similar effects, such as those provided by haste or a speed weapon, nor do they actually grant an extra action, so you can't use it to cast a second spell or otherwise take an extra action in the round. Blessing of fervor does not stack with haste.
So yeah. That is HUGELY important to your allies. It can be quite the game changer, believe me. I use it a lot now with my cleric. Many times I will cast Sanctuary to protect myself, then I will just cast buff spells until either the duration runs out or we need a Bestow Curse to cripple a character.
Bestow Curse and Blindness/Deafness are also mean, however, I get the feeling your cleric is probably playing a boring 'healbot' so I doubt he will even realize these are on the list. In fact, have a cleric baddie cast that so he realizes just how awesome they are.
Also sit down with your players and let them know that you will not be out to kill them BUT they will be challenged correctly instead of metagaming. Remember these important rules and remember both of them.
1. Make a hard encounter that disables one of the party's/characters' tactics. And most importantly:
2. Make sure they can turn the tables using different tactics.
Many people are quick to do number 1 without allowing number 2 and it causes an adversarial relationship between the players and GM. Other people disable multiple tactics to the point where there's only one obscure way to beat the boss. That's bad as well. You want to reward creativity but not force it.
Also, they better nut up and play smart against the fireballs if they don't want to get hit. If a fireball is making them whine, gods help them when you throw down the scary stuff.
It's a common issue if the group is going into one diretion.
Have the same with my lvl 11 group, as long as our enemies are stupid brawlers we will cut throught them like butter, but as soon as they use the terrain, magic or even range weapons we're screwed :D
What was the CR of the enemies? If you put single monster of CR=level they are going down fast: use minions or more monsters a bit less tough.
Also, no trolling intended, but since you are obviously new to the game, why not start at level 1?