Contrariwise, I think that the "addition rather than swap" would work fine, and be appropriate, as long as you also addressed the "the strength here is in the power rather than the class" stuff. For example, maybe taking a multiple-attack power through multiclassing adds "you can add static damage bonuses at most once per round using this power." (Or just apply my personal fave, "any multiattack power - AOE stuff doesn't qualify - adds half static mods to damage instead of full" to the whole campaign and benefit in general.) All Barbarian powers have their explicit bonus die (like Howling Strike's) dependent on an actual Barbarian class feature; in the cases where the bonus is less obvious (e.g. Avalanche Strike), the DM will tell you ahead of time whether he feels it's appropriate to reduce the potency of the Barb power slightly, or not, as he sees fit, and what the new power would read; you can take it or take a different feat, as you like.
Mind you, there are still plenty of folks who are screwed due to the lack of a compatible second class (CON-locks have nobody they can borrow CON-based attacks from), but this might help satisfy the OP's goal.
The other thing you could do is put a span - say three levels - between the level of the power-gain MC feat and the level of the power gained. So if you want to take a feat to add, say, Spitting Cobra Stance to your repertoire, you have to be 8th level to do so.
Or 'spellbook-ize' the power swaps. You can, on a daily basis, pick either the power you swapped into, or the in-class one you swapped away. That would be interesting, actually, and clash very little with the existing MC rules.