you can't expect a class not to have counters, every class has it's own, and mages always countered hpalas , from tbc until now.
It's all about the combo you run and which classes you choose to play with, this game will never be like you want it to be, all classes are equal etc, every comp has it's counter, every class has it's counter.
Thing with Paladins is, there is nothing they bring to a team. They used to work well as the Melee-Healer (both against and with Melee) but the only spec that actually benefits from a paladin now is feral, all other cleaves play with a monk, shaman or priest. Every wizard team they can play (Shatter, LSP etc.) they are just a bad replacement for a druid. They bring nothing for their team exept HoJ, because BoP and Sac are useless against 90% of the teams you meet and their Healing Output without using cooldowns is beyond shit. Their dispel protection is horrible, which makes their only HoT even more useless than it already is. The Spec overall is in a terrible state and the current metagame makes it even worse.