Maybe this is a problem that can be solved by an approach from a different angle. Not sure if it'll help, but I had an idea for some houseruling to make the characters more versatile. Might be an easier/better fix than nerfing the monsters.

In my houserule, characters don't replace encounter/daily powers at 13th+, instead they simply add the new powers to their list of powers known like they did for the first 10 levels. This will increase the amount of bookkeeping players will have to do. Still, for players concerned about verisimilitude , forgetting powers never made any In-Character sense anyway. With this houserule, at 30th level, characters will know 7 encounter powers, 7 daily powers, and 5 utility powers (plus powers from paragon paths and epic destinies).

The idea behind this houserule is that, in some circumstances, the effect of a 15th-level power may be more helpful to the character (and the group) than the high-damage 25th-level power they would have replaced it with in a normal game.

However, characters still have a hard limit of how many of these powers can be used per encounter/day, based on a 'fatigue'-style principle. Play from 1st to 10th remains unchanged. After 11th, each character can use four encounter powers per encounter. After 12th, each character can use four daily powers per day. Characters will only be able to use the same power once per encounter (if an encounter power) or day (if a daily power). (None of these limits account for abilities that allow characters to re-use or regain used powers, such as Reliable powers and some Paragon/Epic abilities). In this way, at-wills should remain about as important as they are in the Core game.

Note that this houserule doesn't allow characters to use a particular, potentially game-breaking power (e.g., Blade Cascade) more often than they otherwise would; they just have more options to choose from when deciding which power to use. Hopefully, by the time characters amass a large number of powers, the player will have a solid understanding of the game and what each individual power does so choosing a power won't take much longer. (Using index cards with the power descriptions on them, as suggested elsewhere, would probably also speed things up if that's important.)

As an Optional, Additional houserule, characters could spend a daily power slot to use an additional encounter power if they wanted to for some reason (but not vice versa). For example, a 13rd-level fighter who has already ran out of encounter powers, but has yet to use all of her dailies, could sacrifice a daily power slot to use an encounter power intead. (I wouldn't expect it'd be too unbalacing if the character wants to sacrifice a use of a daily to re-use a particular encounter power she's already used.)

These houserules do not change the way multiclass power-swapping works, nor allow characters to learn more powers from a second class than they would be able to by Core. Also, these houserules do not change anything about utility powers.