4MSS is a problem, but it's a lot worse from the opponent's perspective. Even if you've determined that it's NP Lucario (meaning that you've already made a risky play to determine whether you're facing the special or physical set), you don't know whether you should send out your Blissey (loses if it has Aura Sphere), Greninja (loses if it has Vacuum Wave), or Aegislash (loses if it has Dark Pulse).
We can't just ban Pokemon for being unpredictable, though. Otherwise we'd be banning Gengar and Aegislash.
His sets tend to have a lot of common checks (Talonflame, Starmie) and counters (Mega Venusaur with Sleep Powder, Gyarados, Zapdos, Moltres, bulky Volcarona) and cripplers (Prankster users) which helps alleviate the problem.