The strength based paladin that is at level 9 has to wait until 10th level before being able to get his daily attack option via the multiclass feats. Divine Power will definitely solve a LOT of problems in terms of lacking options. MAD isn't really a problem as much as the 'half-classes' being underdevelopped.
Starlock is in a bit worse spot ... they didn't actually get a charisma based at-will in arcane power, but at least have some con based paragon paths to chose from. If you choose to go with the con/cha route (to get power versatility) and don't do much with intelligence, you need to get into heavy armor. Similar issue with a melee ranger that wants to go with str and wisdom. Even in PHBII there is one build for the shaman that wants to be in heavy armor, but has to spend feats (and thus still need to put a chunk into str) to get that armor. So, even though they only need 2 stats maxed, they are still MAD to some extent to either be able to wear light armor or get into heavy armor.
Some of it has to do with trade offs though. A strength paladin loses out on divine challenge damage, but can pump wisdom while still keeping 2 NADs doing well. Strength cleric loses out on the healing boost that comes from pumping wisdom, but they can invest in charisma while keeping 2 NADs strong as well. Not to mention, in both cases, multiclassing into str based classes is a bit easier than wisdom/charisma based classes, especially as your weapon will work for most weapon powers, while only divine classes use holy symbols (and the invoker doesn't even use one, so it's only three classes).