Seems fair to me.
Laws of mathematics dictate that as long as the character with 9 initiative is getting a much better "average" over time than he's being rewarded for his input.
Highs and lows are expected in such a system. Even an almighty God Dragon can roll a 1 in D&D and fall on its face for "reasons" And that's part of the appeal
Averages rewarding player stat choice are what counts here overall. The mathematical averages should be what's argued, not outliers. And that just comes down to which algorithm is used.
You said yourself that the RNG works very well for some things. We don't have to make it the standard for everything but I vote that most of all D:OS EE was healthy for the most part and beneficial to the experience
Hell, if you want to be more forgiving as a dev? Alter the weights on rolls for a character with higher initiative such that his minimum rolls feel significantly better than his counter part. It's smoke and mirrors to give the illusion that someone's initiative of 2 simply has a very very very low chance of ever beating 9 cause we make it so, but that all comes down to how you decide implement things
I can see such an implementation making examples like the one you have extreme outliers and thus naturally moot. Hell, if there's a one percent chance of that happening relatively and it does, that's a unique and fun experience in its own way
We're kinda running in circles here, friend. I'm not against randomness in initiative rolls OR initiative rolls for that matter.
My main issues are that
A) initiative rolls still are disadvantageous to the player in a PVE setting where there usually are more foes than friends, especially if the initiative of mobs stays the same (once the initiative of foes is toned down, though, it would be alright, and initiative rolls would be very good in PvP) and
B) I'm against seed saving because it kinda kills randomness, especially if it's followed by restrictions on save games to reduce save scummings, and most importantly, because seed saving can be circumvented.
Were initiative rolls to be implemented with a reduced mob initiative, and without resorting to seed saving and measures to restrict save scumming, I'd be absolutely okay with it.