Yeah. That's a big point. It's pointless to complain about this stuff, but there does seem to be a threshold in competitive games.
SF4's threshold seems to be that they won't allow the creation of a character who has a dragon punch, teleport, a slide/moving low attack, wall dive, and a projectile. You can have a projectile and a slide/moving low attack, but you can't have a dp. They gave Seth a dp, and a projectile, but no slide/moving low(I don't really count his arms or tanden engine). Akuma has no slide/moving low either, and Cammy has a spiral arrow, and a dp, but no projectile. Hakan has slide/moving low, but no dp, and no projectile. Zangief has no projectile, no slide/moving low, and no projectile. Sagat seems the closest to breaking the threshold with his dp, projectile, and low tiger, but he has a slow walk speed.
Characters that would seem to be game breaking would be:
Ibuki with a fireball
Dhalsim with a dp
Ryu with slide
Bison with his fireball(I know he has a fb, just not in SF4) and a dp
Cammy with a fireball
Viper with a fireball
Vega with a fireball
Zangief with a fireball
T.Hawk with a gun
I can't really speak for modern NRS games, but the issues that cause their old games to have "balance" issues center around walkspeed/retreat walkspeed, projectile speed/properties, and tool allocation(giving too much) and not allowing enough defensive options.
Fair vs Unfair is not really a good question. Competition in general isn't fair: someone will win and others will lose. The question is what is reasonable for some characters to have and what isn't(threshold). A character like Kabal is right at the NRS threshold imo because the only move he doesn't have is a NRS style vertical/horizontal opposite teleport. MMH has a teleport, but does he also have a low projectile?
Kabal is close to a perfect character design(swiss army knife character/master key character is what I call them) for a 2d NRS/Midway style game imo, outside of a design that just wins on damage and reset potential. You don't want to create a perfect character because that would defeat the purpose of the game. For example, the queen can move in any direction in chess except the "L" shape of the knight, but she has no way to mate the king by herself(she needs help). Similarly, you don't want to design characters that can cover nearly all situations or every situation.
Barring infinites or T.O.D combos/resets, NRS/midway threshold seems to be a character with:
projectile, mid air projectile, low projectile/slide, vertical/horizontal opposite teleport, an overhead, an unblockable full screen projectile, full screen dash, and a move that cancels on block/hit.
Kabal has 6/8 of those attacks.
SF4 characters seem to have 2/5, 1/5 or 0/5 of their threshold attacks.