I read an old thread on this forum about overpowered decks. One poster said that it was easy to fix dwarves by just banning Dain, but that it was harder to fix Outlands. His suggestion was to ban the Anfalas Herdman, so that all outland allies remained squishy with one single hit point.
I think there is a better way: don't allow Outlands bonuses to stack. In other words, Knight of the Swan only gives Outlands allies +1 attack, regardless of whether you have one or all three in play. If you have all four types of allies in play, Outland allies get +1 willpower, +1 attack, +1 defense and +1 hit point.
This is a big nerf, but the Outlands deck should still be competitive. It is fairly easy to get one of each ally in play, and max out the bonus. A 2 cost ally with stats 2, 2, 2, 2 is still a really good ally.
1 cost Outland allies max stats: 1, 1, 1, 2.
2 cost Outland allies max stats: 2, 2, 2, 2.
3 cost Forlong (which refreshes every phase) max stats: 2, 2, 2, 4.
Hirluin the Fair max stats: 2, 2, 2, 5.