So for me, discussing the issue and possible solutions isn't merely idle speculation. It has relevance for how I idle away my hours by RPGing!
Well, I have a possible idea for a solution to the various issues that have been raised. Of course, people don't seem to agree with me, but it won't stop me from trying!
I would suggest (again!) that magic be different than mundane feats. Not necessarily better, not dominating, just feels different and (literally) magical. ie., you have one rules paradigm for melee/ranged combat, and another rules paradigm for magical effects. This means that there are things you can do mundanely that cannot be duplicated by magic, and there are things you can do magically or supernaturally that cannot be duplicated in the mundane world.
This doesn't mean that playing a pure fighter is boring. There are many interesting combat maneuvers and combat stances (a concept from Jester's D&D Jazz) and other tactical advantages. A fighter should always feel useful and significant. At the end of the day, a sword thrust into the belly is always going to the most reliable way to kill someone.
It would, however, probably mean that 4E fighters lose any wushu-style feel... at least at low levels. At high levels, a warrior might do mundane but extraordinary feats, but it wouldn't be magical. It would be impossibly improbable, like always splitting an arrow with a second arrow shot.
Conversely, magic would truly feel unique, a power source from another world, which is what it's supposed to be according to literature and archetypes. This contrast to the mundane would allow players of wizards to feel "special" without necessariy being dominant. This does NOT mean casting magic missile every round like it was a mundane crossbow. It means casting a magic missile that swerves left and right and up and down as it bears down on the enemy like a heat-seeking missile, an effect that's not merely improbable but mundanely impossible. It also means having access to versatile utility spells and rituals without necessarily tons of gold as a meta-balance mechanism.
It would also mean that wizards don't get access to magic all the time, because nothing feels truly magical or dramatic when it's continously watered down for the sake of balance. That means that wizards probably should be semi-capable fighters, like Gandalf, during any 'magical downtime'.
If you want to have a bit of both, then you play a class that combines magic and mundane, like a shadow thief or divine paladin or rune-warrior concept.
For me, it also requires sometimes coloring outside the 4E lines. Magic needs to spill outside the box to reach its full creative potential. If you create a new plant-and-vegetable mage, you don't have to create a Fruit-to-Veggie teleport power ("if you hold a fruit in one square, you may teleport to any vegetable within 6 squares"), simply because 'teleport' is one of 12 pre-programmed allowable actions. I would imagine what a plant-and-vegetable mage could do, and then create new rules for it if necessary, and if it's truly unbalancing or truly incompatible with the current ruleset, I think it's better to completely ditch the concept, instead of catering to public health demand and producing a sub-par plant-and-vegetable mage.
I suppose that, if mundane and magical rulesets are not directly comparable, the pro-balance side will have fits trying to mathematically measure for balance issues, and the only way to balance is through old-fashioned playtesting. I just don't have much sympathy for the approach of making everyone "the same" so that you feel more certain about measuring for balance.
Finally, as pemerton kinda touched upon, it would be nice to have a tweaking mechanism for how the magic ruleset layer meets the core mundane ruleset. This would allow for a gritty low-magic campaign or a high-magic superhero/wushu campaign.
All of this, of course, is entirely theoretical. I have no idea how it would play out in practice, or if other game systems take this approach.