Let's be honest here, has Mega-Lucario ever been THAT much of a problem for you? It's a glass cannon, and is easily outsped by anything with a scarf. Let's use Darmanitan as an example. Lucario only has Vaccum Wave, Extreme Speed, and Bullet punch for priority.
Let's run some calcs.
252 Atk Sheer Force Darmanitan Flare Blitz vs. 0 HP / 0 Def Mega Lucario: 600-708 (213.5 - 251.9%) -- guaranteed OHKO
252 Atk Adaptability Mega Lucario Bullet Punch vs. 0 HP / 0 Def Darmanitan: 77-91 (21.9 - 25.9%) -- 3.7% chance to 4HKO
252- SpA Adaptability Mega Lucario Vacuum Wave vs. 0 HP / 4 SpD Darmanitan: 134-158 (38.1 - 45%) -- guaranteed 3HKO
252 Atk Mega Lucario Extreme Speed vs. 0 HP / 0 Def Darmanitan: 153-181 (43.5 - 51.5%) -- 9% chance to 2HKO
252 Atk Adaptability Mega Lucario Close Combat vs. 0 HP / 0 Def Darmanitan: 458-540 (130.4 - 153.8%) -- guaranteed OHKO
Now I get that these aren't boosted, and that Darmanitan is only a check because it can't switch in safely against something like a Close Combat, but it is something. I can't think of a counter right off the top of my head, because I've never really had to think about a counter for him, because he's never been that big of a threat to my team.
Pokemon like Landorus can easily check the physical variant. Gyarados too, you don't need to mega evolve. Quagsire, depending on what kind of bulk you run, can be a good option too. And the only thing that people run on Lucario that can touch Charizard is Extreme Speed.
Now as for Genesect, he isn't a problem either. A fire move from ANYTHING can take it down. I get that it has mediocre defenses and can survive neutral hits easily, but c'mon now.
Deoxys-S.... I have nothing to say. Why? I don't even know. Not even that common to be that much of a threat. It can taunt, and set-up easily. But it doesn't have much offensive potential. Move it up to OU if you must, but there is no reason for it to go up to Ubers...
I am starting to notice a pattern here. I know this is being suspected for now, but Smogon, whenever it bans something, bans the next most powerful pokemon because it's "too good" for the metagame. Lucario may have the most offensive potential ATM, but he is by no means "too good". Or broken for that matter.
P.S: Smogon, PLEASE OH PLEASE tell us the reason why you think said pokemon should be suspected. It would be much, MUCH easier for us to have a discussion.