Disclaimer - I'll state this right out at the front. I think game first is superior design. I'm going to try to be as even handed as I can here, but, I do feel that game first is the better way to go.
I don't think it really matters what you start with, as long as you end up with non-dissociated mechanics that are fun to use.
Generally I design a world and then make mechanics that both (a) work and (b) describe it, because I think it's generally more interesting to start with the awesome and then make the numbers work, rather than trying to figure out ways to make numbers sound awesome.
But, is there a class that has caused more problems at the table than the paladin? From day 1, the paladin has caused all sorts of issues at the table. Frustration and outright hostility quite often. The flavour says that the holy knight should only work with other good characters.
Plus, I think your thesis is kinda broken. D&D started out by kitbashing a wargame -- it was hardly a "flavour-first" design methodology.
For example, paladins were weighted down with lots of limitations because they were considered a superior class. So what you're claiming is "flavour-first" design was, in fact, "game-first" design.
But, then you hit the table. And the poor rogue player is sitting in the corner twiddling his thumbs because his one main combat ability is nerfed entirely by about a quarter of the creature types out there. In a tomb raider scenario, quintessentially D&D, the rogue is reduced to the role of well armed commoner by pretty much any monster most likely to inhabit a tomb.
But, on the flip-side, all of the rogue's non-combat abilities (finding traps, opening locks, etc.) are at their most useful during a tomb raider scenario.
To me this complaint about the rogue not being able to backstab everything in sight is like the arcanist complaining that some creatures have spell resistance.
You can't use your bestest ability all of the time?
I weep you for. They're crocodile tears, mind you. But I weep for you.
The other problem was in PrC design that narrowed the focus based on the flavour. Knight of the Chalice (at least the 3e version) is a poster boy here. A PrC that gives you massive bonuses against demons, because that's their purpose - kill demons. But, what if the DM doesn't use a lot of demons, just some?
Then you probably shouldn't be playing a Knight of the Chalice in that campaign. Ditto to your Ranger complaint.
Similarly, if you're playing in a campaign without a lot of combat, you shouldn't play a fighter. If you're playing in a campaign set entirely with an antimagic zone, you shouldn't play a wizard. If you're playing a campaign in which the PCs are an elite team of political assassins, you shouldn't play a paladin.
Yada yada yada.
Some people apparently want all classes to be all things at all times. Personally, I find that lack of variety pretty boring.