So I'm seeing only a few organized nations from your description, which I'm also seeing as a lot of blank space to explore. The great point here is that you can apply that to both types of players along the political-to-murderhobo spectrum. Murderhobos just need a patron to point them at a dungeon. Politically savvy players will enjoy having multiple patrons with conflicting goals, all of which can collide either in the wilderness or in a civilized setting, so it's more a question of how you present the hooks.
I guess I'm a little confused by this. How would you say bandit gangs are anachronistic? I would say that bandits arise from a breakdown of central authority. Central authority can be either present or absent in high fantasy, so I'd argue bandits are perfectly viable. However, if you're thinking that bandit gangs couldn't compete with powerful mages, then the solution is simple: the bandit gangs are run by magi. Maybe some of these gangs are run by mage-school dropouts, little better than sadistic thugs with heat metal and a rod. But maybe some bandit gangs are actually run by a mage patron who handles arcane countermeasures (casting nondetection or supplying the bandits with amulets of proof against detection and location for example). What if a powerful mage has several bandit gangs on the payroll, and each of them have contingent spells set up so that if the bandits try to rat them out under interrogation, the bandits suffer some horrible fate (fireball? dominate person? brain melting? Knock yourself out!). There's a lot you can do there.
Hells yeah, brother!
Yeah, I'd definitely recommend Eberron as inspiration, then. Sounds like exactly what you're going for.
Disregard this point; it doesn't apply to 3.5. I remember the Dark Times.