To begin with, I want to say that I am really happy about someone still playing 3.x, and keeping the Sohei in mind, and your feat suggestion was very good and gave me a lot of ideas. I agree that using a partial gestalt is the way to go, too, though I feel it may not be THE best solution. The reasons why, below.
I'm pretty confused about a couple of things. To begin with, you recognize (as does anyone who has ever played a Sohei), that it is in HUGE need of add-ons, both in the way of feat support and PrCs options.
Therefore, I understand you looking towards gestalt as an easy fix, but it only makes me more confused because:
1 – You handily ignored the Rokugan splatbooks. This is incredibly confusing for me because, while I'll be the 1st to agree on the fact that they are 3rd party stuff, and 3e, and therefore need a lot of updating, they were at least writen by professionals, and most people would therefore give them more credibility than fan-made, homebrewed stuff.
That being said, I am fully aware of some really weird ass mistakes made by 'pros' as well. I'm looking at you, Complete Divine! Jesus, the Rainbow Servant alone has SO many mistakes plastered all over it that you would easily throw it into the garbage bin if you didn't look online for erratas and official replies from customer service to it, just to mention an example of 'pros' fucking it up.
Anyway, yeah... it really, truly baffles me that you are okay suggesting fan-made, homebrewed solutions and 'ask your GM to look the other way and pretend ki frenzy equals rage' and stuff like that, but apparently forgot to even look at what the Rokugan campaign setting splatbooks may offer the Sohei,
Just to begin mentioning a few things.
Void Use – This feat gives you 2 Void Points, of which you can spend one at any time to increase your armor by +2 (Void bonus) until the beginning of your next turn, or increase ANY roll (except for damage) by +2. It may look like a pretty humble thing, but it is important because of the following feats.
Depths of the Void – This feat just gives you +2 extra void points. Again, extremely straightforward and noone is gonna get exctied about it, but it is a requisite for the following two feats.
Blessing of the Void – A Phoenix clan-only feat. You get your character level/3 as Void Points, which means that if you are level 6+, you are already not losing anything on by picking it up, and it scales as you level up. You probably will want to consider this one, or the following feat.
Greater Depths of the Void – Also a Phoenix Clan exclusive, it gives you 4 Void Points, plus 1 more void point per each time you take this feat, so if you take it twice, each gives you +5 Void Points. Take it thrice, each gives you +6... etc. You don't NEED Bleesing of the Void for it, just Greater Depths of the Void. GtoV may be better if you are only planning in having a few void points, but you probably are not, because of the next feat-
From the Ashes – Phoenix Clan-only feat that, whenever you die, lets you automatically spend 2 Void Points to ressurrect yourself with double the amount of Void Points you had before using this feat, as temporal hit points. This means that with 25 Void Points, you die and get resurrected instantly with 50hp, then if you die again, get ressurrected with 46hp, then if you die again, get ressurrected with 42hp... 38hp, 34hp, 30hp, 26hp, 22hp, 18hp, 14hp, 10hp. 6Hp, 2hp... at this point, you basically have +328 temporal hp available to you, which makes you a fucking fantastic tank. Remember you have Shield Other as a Sohei spell, heavy armor proficiency, excellent Fort and Will saves, plus motherloving Mettle, meaning you will NOT die to save-or-die effects, and you are an OUTSTANDING tank.
Oh, and Way of the Phoenix (Phoenix exclusive feat, of course) allows you to spend ANY number of Void Points in any one roll, so all those Greater Depths of the Void feats you probably took are really, really handy, even if you have no plans to die yet, because now you can raise any roll (except damage) by +2 each time you use a Void Point (void bonuses stack).
Furthermore, Furious Guided Blows is a feat that doubles your void bonus to attack rolls from +2 to +4, and even gives you a free +1 on your next attack roll after the one you are enhancing with it.
Hell, there's a phoenix feat which even lets you make extra attacks with your max BAB for the cheap price of 3 Void Points. Surprising noone, its a phoenix feat. Anyway, you can see how a Phoenix Sohei can be a frikkin nightmare to put down.
Anyway, each clan has a few feats that make a Sohei into a nightmare. For example, the Scorpion clan has a feat that adds your Int mod to initiative, which really helps with your iaijutsu focus.
Oh, and scorpion and crane clans share a feat called Speed of the Kami which doubles your Void Bonus to initiative, if you happen to spend a Void Point to raise your initiative. Oh and don't forget, you can add Void Bonus to your skills, so Iaijutsu Focus is pretty tasty.
While speaking of the Scorpion clan, they have a wonderful feat called The Pincers Hold, the Tail Strikes, which says “whenever you attack a flat-footed opponent, your attack is an automatic critical threat”, which is sooo sweet with a naginata. Remember, naginata have x3 critical hit damage. Just Just get the feat that gives you a +4 to confirm your critical hits, and you basically get +4 to attack all the time against flatfooted opponents. Which, with your speed, should be pretty much everyone, anyway.
Crane clan has feats which gives you extra attacks and/or attack bonuses against anyone with a lower initiative than yours, so have fun with that.
Oh! I almost forgot, either the phoenix or the crane (but I thiiiink its the crane?) has a feat that gives you +4 to attacks against opponents with a lower Void Point total than you, so, have fun with that. Suddenly, that ¾ attack looks mighty reasonable, when you remember you can get +4 (because they have less Void Points than you, passively) +1 from weapon focus, +2 (or +4 from Furious Guided Strikes if you are a phoenix)... etc bonuses to hit.
So yeah, if you are okay using things like partial gestalt to 'fix' the sohei, maaaaaybe you should at least look at the splatbooks within the setting it was meant to be played in?
2 - Prestige Classes and/or multiclassing. Again, you didn't look at the Rokugan splatbooks, did you? But without going too far into them...
Bear Warrior – I agree with you in that this is a great choice. Specially if you take the dragon clan martial arts feats, which let you start a free grapple whenever you hit an opponent with an unarmed attack, have you count as one size category larger for grapple checks, and even let you start grapple checks against opponents 5' out of your actual reach, then render them unconscious automatically if you pin your opponent for 1 round.
Personally, the crab clan martial arts are way more hilarious, though. You basically trip your opponent, mount him, and proceed to punch him in the face, repeatedly. Oh those wonderfully simple but hilarious crabs! Do this as a bear, and its just extra funny.
Oh, going into splatbooks, you probably want to look at the phoenix clan Heavenly Wing Initiate, since it allows you to use the Heavenly Wing kata (basically a stance. You pay exp to learn it, use it with the naginata, and then 'hold it ready' for 30 minutes) for 3 hours after you ready it, instead of the normal 30 minutes. What does the PrCs do? It is a wonderful PrCs only 5 levels long which gives you free void points, because lord knows the phoenix clan likes them Void Points, full BAB, good saves, and d10HD,
Oh, the Heavenly Wing Kata, when 'discharged' lets you do 1 attack at your highest attack bonus for each Void Point your maximum Void Point pool can hold. Not even by how many you have, but by how many you can have.
So, lets say you go bananas on someone, that's probably 25+ free attacks with your highest attack bonus against that someone. Afterwards, you're fatigued for 1 minute per extra attack, but we all know that's not really anything new or anything we hadn't had to deal with as a Sohei before, right? Just get a couple of sandals that help you with that.
Or don't. Odds are that whatever you just did 26+ attacks on, is probably dead. If it isn't dead, you probably weren't going to kill it anyways. Oh, and you can take 5' steps in between attacks if you are a lvl 5 Heavenly Wing Initiate. Just glorious.
Lion clan martial arts are funny. You use a... what is it called... its like a trident, but for farm work. You know, one of those things you haul packs of straw with? Anyway, this martial art makes it worth your while for you to pick weapon focus with this simple weapon, because you can basically poince with it, and whenever you hit someone, you start an automated grapple with it, at range, because this martial arts assumes you impale your opponent, then LIFT him off the ground and keep him impaled.
Do not fuck with the lion's peasants.
Anyway, my point is that you really should look at the whole picture, because if you are okay bringing in online solutions and asking your gm for special favors, you may as well first look at all your options, no?
Other than that, awesome work! I really truly liked some of your feat and multiclass suggestions, and feel they will greatly improve my future Sohei characters, thankyou!
Edit: Btw everything I just said goes double for the samurai, triple for the ninja (though I swear you should take at least 1 rogue level on it if you wanna be useful), and quadruple for the Shugenja. A level 8 fire spell lets you cast 3rd level fire spells as free action, at a cost of 1 Void Point per spell, so a phoenix (who happens to love fire spells and typically have the most Void Points in the game) are goddamn horrifying.
There's also an earth spell which gives you and your party members their honor (basically brownie points you get for being a generally heroic fella. You know, stuff like "oh, your group arrested the gang that had been terrorizing our village, we are so grateful, noble ones!" and "I know it must have been a painful decision to give up the powerful item to your lord, but it was the honorable thing to do") + their charisma modifier as a buff to Str, Dex and Con, plus DR 30/obsidian (yeah obsidian weapons are a thing in Rokugan) for 1 minute per level you have.
Or 9th level fire spells that cause a target to explode into flames for 20d6 damage every round... forever.
Or 9th level water spells which randomly and instantly rearrange all of a terget's stats. "Oh, your str? Yeah, roll 1d6 and see what it gets switched with. Oh, you got a 6? It gets switched with your Charisma. Yes, this is forever."
Or ... well you get the idea.
Samurai probably get the most mileage out of the splatbooks, though, but the Sohei gets pumped up a couple of tiers, IMHO. Its still tier 4, but definitively no longer tier 6 ir 5. I'd still suggest partial gestatlt with a warrior, or maybe a fighter, for the bonus feats... so you can use your regular feats to get more Void Points.