Having faced an endless stream of Paladins on ladder I decided to look at the card sets for standard and I noticed that Paladin's core set is actually pretty weak. The core set only contains three cards (all secrets) that are being regularly played on ladder right now. Literally all of Paladin's power lies in the four expansion sets that are currently in standard. Each set has supported the three main archetypes that paladin currently has.
Scholomance + Darkmoon: Aggro
The issue as I see it is that in the current meta Paladin has access to three separate pools of really powerful cards. And since most of them are tempo cards, they can be mixed and matched (secret libram for example) to create decks that are totally busted. No other class has the ability to do this. Take Shaman for example. They have cards that support murlocs, elementals, spell power, and aggro, but none of the cards really work together as a mix + match, let alone as a specific archetype.
All that being said IMO blizzard has to do a better job of balancing in the future to ensure that more of Paladin's core cards see some amount of play. I'm not sure exactly how they will do that, but otherwise paladin's power will continue to rely heavily on expansion cards and we may be in for another two years of Paladinstone.