It's a very simple formula: Simple and fun combo system, smooth gameplay and unique character design.
I think that's why, even though the Neatherrealms games (Mortal Kombat and Injustice) are enjoyable enough they don't hold their own against Street Fighter, Marvel Vs. Capcom, King of Fighters, Guilty Gear, or BlazBlue. They have the combo system right, but they're certainly missing the smooth gameplay and unique character design.
Also, A gimmick doesn't hurt (ie, parry system, focus attack, X-Ray, burst system, combo breaker etc).
And "overly complex" isn't the case with fighting games. What you call overly complex is just depth. Fighting games are naturally very shallow: it's just P1 vs P2 (possibly more in a arena style game), but the depth is needed to seperate the good players from the average; aand to stop players from getting bored of the game quickly by offering a learning curve and a challenge for the player to overcome. Fighting games, especially at a higher level get very technical, but you might not have expected it because of its p1 vs p2 premise. The frame data, spacing, mind-games, blocking mix-ups, parrying, performing difficult combos, knowing when to do what, etc (pretty much everything that could be considered complex) is what makes the fighters skill based games. And why it's so satisfying to go 1 v1 against someone else.
