I have the same problem, although mine's not nearly as bad. I've recently gotten into the habit of calculating their APL according to the Monster Creation Chart. So my level 17 ubercharger's mount has a series of attacks all his own which amount to a CR 25 creature, the Mounts AC is around a Cr 22, and his saves are around a CR 15.
Cr25+CR22+Cr15 = 32. Divide 32 by 3 and you find out that his basic hyjinx of attacks and defenses are around a CR 20.5 creature.
(The stats I used to figure it out was "Average HP, AC, Saves, Average Total Damage if all their attacks hit and don't crit, and the DCs of any special abilities they had.
I've done this to all my players, and their pets. (Yes, I'm including all my pc's pets as part of the APL), after adding it all up and dividing by the total number of players and their pets, the total APL comes out to a CR20.
So now, I start the +4/-4 APL at 20 for them. If they encounter a really difficult fight, it's a CR 24. if it's a rather easy fight it's between 16-20.
Before I came up with these statistics, my party was at at most fighting CR21 for their hardest encounters and breezing through them. And that's why - because even though the entire party was all level 17, their "actual" level was far higher. A CR 21 fight was just a +1 CR than an "average" fight for them.
Prepare all your encounters according to their "actual" level and you'll have no problem.
If you really wanted to be a sneaky DM - give them XP according to the total number of assets in their party (in other words, treat each pet participating in the battle as though they grabbed XP as well, and give the party the remainder to divide). This will stop them from hyper leveling, since they'd be getting an influx of XP and possibly the game would scale faster than you want it to.