Help me buff out an Efreeti

Question

Continuing the advancement of the efreeti in this question, I try to figure out the gains of an efreeti advanced to 16 HD. After advancing it and achieving the huge size as indicated by its new HD, I want it to use its enlarge ability to reach the gargantuan size. So I figured out that in gargantuan form (after being huge because of its HD and after using its enlarge ability) the efreeti will now have the following stats:
+ 6 BAB
+6d8 HD
+16 STR
+8 CON
+7 natural armor
-2 DEX
-3 AC/ATTACK (due to size changes)
Slam attack will go to 3d6 from 1d8 and
+2 feats due to HD.

Now my question is if I got the stats adjustment right, or need any corrections. As a bonus question, please propose a way to prevent this gargantuan outsider being one-hit KOd by a frozen attack (see frozen vulnerability). Magic items or spells are allowed, as this is going to be a boss and has minions, including spellcasters.

Edit (more info). The reason I'm trying to advance this monster is to create a challenging boss for this kind of party: levels 11-12. Wizard - blaster, Cleric buffer - support, Barbarian damage inflicter and a new rogue/ranger which a player will be playing for the first time, as his old rogue character met a horrible death. They have been able to fight monsters and characters at average party level + 2-3 until now without much of a sweat. The only times they have been close to death is when the wizard is disabled in someway and they are denied his massive damage/round.

Answer 1

An Efreeti with minions and time is a terrifying terrifying thing.

Presuming 16 HD, that gives us 6 levels to play with. The efreeti isn't particularly smart, which suggests that with one of his feats (leadership), he'll have a "grand vizier (pointy beard required) psion or wizard or bard/sublime chord." More to the point, being lawful evil, he'll have struck a very sensible deal with his followers: "In strict rotation, according to this rota maintained by my visier, each of you may use my wish ability in a grand ceremony at the end of the day. Two of your wishes will be to my benefit, and the last may be to your own benefit, chosen from this catalogue."

As the consequence of this proclamation, the danger of the efreeti comes from his followers, each of whom have every slot filled with a magic item costing exactly 25,000 gp. Every attribute of every follower will have a +3 applied to it (because being rational this genie will allow his followers to batch up their wishes for this purpose.)

Therefore, given that the bulk of optimisation will happen in the level N-2 "grand vizier" who is quite happy being where he is, we can just have fun with the 6 levels on top of the efreeti, who being intelligent will not take the feats in his statblock. Critical feats are: Leadership and Mindsight

Beyond this,it's a function of how much time the Efreeti has had to prepare in his current location and what magic items you feel like giving his minions. The effective way to defeat this guy is to turn the grand vizier rather than a straight up fight, since the vizier can always use an action to invoke the three wishes and port the most annoying bits of the party to nasty nasty planes.

Answer 2

The players problems in this are going to be twofold. A smart efreeti is going to cover up his vulnerabilities to cold with Protection from Energy, which will absorb 120 points of cold damage at CL10 and allow him to deal damage that much longer. He will probably also use Invisibility to get the drop on the PCs as well, which gives him a surprise round. Don't forget that there are all manner of Abjurations he can have cast on himself to protect himself from the PCS as well.

Maximizing the Mailman

Use of the mailman to deliver the mail in this fight is going to be essential to survival. You're going to need to take out something with that kind of advancement very quickly, and the mailman will either have the damage to deal with the problem or a Save or Suck that they can throw out to get rid of his buffs so that the mail will make it on time. If the mailman gets taken out, you might have a TPK on your hands.

Dealing with Gaseous form / Plane Shift

When your big bad gets messed up, he's going to flee. And he's probably going to utilize one of the two above spells to do so. If you want him to flee? That's great. He has a way to escape instantaneously should the situation go awry or should his toadies get their faces smashed in by your barbarian. But if you want him to die that poses a problem because it means that your casters are going to have to use Dimensional Anchor to root him to the plane they're fighting on.