They ought to be stronger, more dexterous, and hardier than efreet... but do we dare give them a +10 natural armor? Perhaps a Deflection bonus to their Armor Class? I've only seen those bonuses occasionally, and don't quite remember if Deflection bonuses are only for certain types of creatures.
Yes we should dare! These things ought to be really nasty in a fight. They've got to fight off PCs, remember.
They're as Strong as AD&D Stone Giants (Str 20, but Str 27 in 3E) and their -4 surprise adjustment is the same as for AD&D Dex 19-20 if I remember rightly.
A rhinoceros has a +7 NA bonus in 3E doesn't it? I'd like to add on another bonus for the "magical nature make them very difficult to hit"?
So I'm thinking:
Abilities: Str 26, Dex 19, Con 16, Int 14, Wis 15, Cha 15, +7 NA, +4 deflection
Deflect Attacks (Su): A guardian genie gains a +4 deflection bonus to its AC if it is not wearing any armour.
Maybe bigger damage dice. Certainly they ought to have the Improved Initiative and Multiattack feats, possibly Alertness but we can easily devote a nice chuck of the Skill Ranks to Listen, Search, and Spot as well as racial bonuses.
Djinn and Efreet get Improved Initiative as a bonus feat, so I reckon the Guardian Genie ought to as well.
I'd just give them a modified form of the Marilith's natural multiweapon ability. It'd be simpler... and nastier.
Combat
Each of a guardian genie’s four arms can wield a melee or throwing weapon without penalty, and the creature can make full iterative attacks with its primary arm.
As for the damage, I'd be fine with giving them 1d8 slams like the SRD efreet or djinn but would rather boost its natural attacks to 1d10 like the original draft.
Now I know it says they prefer scimitars but I'd rather give them Large longswords, since it'll give 2d6 damage instead of 1d8. Just imagine each longsword is a "cutlass" or "great scimitar".
Oh, and throwing axes for ranged attacks.
They ought to get the benefit of something like Ubiquitous Vision, possibly as a supernatural ability:
...In effect, you have a 360-degree sphere of sight, allowing you a perfect view of creatures that might otherwise flank you. Thus, flanking opponents gain no bonus on their attack rolls, and rogues are denied their sneak attack ability because you do not lose your Dexterity bonus (but they may still sneak attack you if you are caught flat-footed). Your Spot and Search checks gain a +4 enhancement bonus. Concurrently, you take a -4 penalty on saves against all gaze attacks during the power’s duration.
That looks good!
So my proposal is something like:
Genie, Tasked, Guardian
Hit Dice: 14d8+42 (105)
Initiative: +8
Speed: 40 ft.
AC: 24 (-1 size, +4 Dex, +4 deflection, +7 natural), touch 17, flat-footed 20
BAB/Grapple: +14/+25
Attack: Longsword +20 (2d6+8/19-20) or slam +20 (1d10+8);
Full Attack: Longsword +20/+15/+10 (2d6+8/19-20) and 3 longswords +20 (2d6+4/19-20); or 4 slams +20 (1d10+8)
Saves: Fort +12, Ref +13, Will +11
Abilities: Str 26, Dex 19, Con 16, Int 14, Wis 15, Cha 15
Feats: Improved Initiative (B), plus 5 others