There are more ways to counter MLuc than people realize. Any one set it runs isn't perfect and can be walled by a number of standard OU mons. Special MLuc can be stopped by a number of pokemon who have either have assault vest (like Conkeldurr) or resist its stabs (like Zapdos). Special MLuc has to choose between priority or better coverage. Physical MLuc is probably the most balanced set and has the very scary adaptability cc, but it has to worry about burns, intimidate, rough skin/rocky helmet, spiky/king's shield, gooey/static/flame body, etc. Mixed MLuc forgoes priority, coverage, and/or boosting for its surprise factor.
Many people have stressed that the counters for each set vary drastically and guessing wrong can often mean you lose 1-6 mons. Some even say he has no true counters or that any would-be counters are a liability otherwise. I'd like to try and show that he can be countered.
+2 252 Atk Adaptability Mega Lucario Close Combat vs. 244 HP / 252 Def Heracross: 268-316 (74 - 87.2%) -- guaranteed 2HKO after Stealth Rock
+2 252 SpA Adaptability Mega Lucario Flash Cannon vs. 244 HP / 0 SpD Assault Vest Heracross: 258-304 (71.2 - 83.9%) -- guaranteed 2HKO after Stealth Rock
0+ Atk Heracross Close Combat vs. 0 HP / 0 Def Mega Lucario: 384-452 (136.6 - 160.8%) -- guaranteed OHKO
As you can see, Hercules is very tanky and hits like a truck. There were 12 EV's to spare here. You could also do scarf Hera or MHera and have the same potential to switch in on anything it does and kill it. Outside of countering MLuc he can status absorb with guts, take hits like a champ, and hit back hard with cc, eq, megahorn, and rock blast/stone edge.
+2 252 Atk Mega Lucario Crunch vs. 252 HP / 52 Def Aegislash-Shield: 256-302 (79 - 93.2%) -- guaranteed 2HKO after Stealth Rock
+2 252 SpA Mega Lucario Dark Pulse vs. 252 HP / 16 SpD Aegislash-Shield: 256-302 (79 - 93.2%) -- guaranteed 2HKO after Stealth Rock
56+ Atk Expert Belt Aegislash-Blade Sacred Sword vs. 0 HP / 0 Def Mega Lucario: 283-334 (100.7 - 118.8%) -- guaranteed OHKO
If you don't want attack boosting nature and expert belt, you can invest as little as 44 in Atk and rely on shadow sneak to kill it after sacred sword. Special MLuc can't hit you with priority and Physical MLuc can only do it with bullet punch, which opens up the king's shield mind games. Just having this guy on your team should make MLuc hesitate to boost on any potential free turns (if you switch in when he boosts, he either switches out or dies). You could also do air balloon/shuca berry if you were afraid of eq ruining your day. With leftovers you don't need any Def/Sp Def EV's to survive after SR.
+2 252 Atk Mega Lucario Crunch vs. 240 HP / 56 Def Slowbro: 330-390 (84.3 - 99.7%) -- guaranteed 2HKO (as long as SR is down you can beat it)
+2 252 SpA Mega Lucario Dark Pulse vs. 240 HP / 8 SpD Assault Vest Slowbro: 294-346 (75.1 - 88.4%) -- 6.3% chance to OHKO after Stealth Rock
204+ SpA Slowbro Fire Blast vs. 0 HP / 4 SpD Mega Lucario: 282-332 (100.3 - 118.1%) -- guaranteed OHKO
Slowbro when EV'd properly can survive and OHKO back. With regenerator you aren't crippled if he chooses to switch out after attacking. He isn't SR proof physically, but being able to counter both sets is impressive. He is a good pivot outside of countering MLuc hitting with impressive fire/fight(or psyshock)/water/ice coverage.
+2 252 Atk Adaptability Mega Lucario Close Combat vs. 232 HP / 192 Def Volcarona: 312-368 (84.5 - 99.7%) -- guaranteed 2HKO
+2 252 SpA Adaptability Mega Lucario Aura Sphere vs. 232 HP / 0 SpD Volcarona: 177-209 (47.9 - 56.6%) -- 35.5% chance to 2HKO
+2 252 SpA Adaptability Mega Lucario Aura Sphere vs. 232 HP / 192 SpD Volcarona: 148-175 (40.1 - 47.4%) -- guaranteed 2HKO after Stealth Rock (If you choose to prioritize countering Special MLuc)
16+ SpA Volcarona Fiery Dance vs. 0 HP / 4 SpD Mega Lucario: 332-392 (118.1 - 139.5%) -- guaranteed OHKO
You can switch in on Special MLuc and quiver dance+roost/fiery dance or just kill it asap. Physical MLuc requires Stone Edge to kill you. 68 EV's in speed. Bulky Volc shouldn't be underestimated. Being able to set up on one of the best special sweepers in the game says a lot. Flame body hax is also rq inducing frustration just waiting to happen.
+2 252 Atk Adaptability Mega Lucario Close Combat vs. 252 HP / 200 Def Amoonguss: 296-349 (68.5 - 80.7%) -- guaranteed 2HKO after Stealth Rock
+2 252 Atk Mega Lucario Ice Punch vs. 252 HP / 200 Def Amoonguss: 370-436 (85.6 - 100.9%) -- 6.3% chance to OHKO
+2 252 SpA Adaptability Mega Lucario Flash Cannon vs. 252 HP / 56+ SpD Amoonguss: 376-444 (87 - 102.7%) -- 18.8% chance to OHKO
Amoongus has regenerator and spore. He can take the strongest hits on both sides (most of the time) and get off a spore. You could specialize him to take hits better from whatever side you fear more. Phys MLuc w/o ice punch can be dealt with even under SR. Not really a true counter, but he does force him out w/o dying in the process. If he doesn't switch out, you have a free switch in to whatever can normally revenge it (1 turn of sleep is guaranteed and 33% chance he wakes up turn 2)
252 Atk Adaptability Mega Lucario Close Combat vs. 252 HP / 132 Def Nidoking: 150-177 (40.9 - 48.3%) -- guaranteed 3HKO
252 Atk Mega Lucario Ice Punch vs. 252 HP / 132 Def Nidoking: 188-222 (51.3 - 60.6%) -- guaranteed 2HKO
252 SpA Adaptability Mega Lucario Flash Cannon vs. 252 HP / 8 SpD Nidoking: 232-274 (63.3 - 74.8%) -- guaranteed 2HKO
252 SpA Adaptability Mega Lucario Vacuum Wave vs. 252 HP / 8 SpD Nidoking: 58-69 (15.8 - 18.8%) -- possible 6HKO
252 Atk Adaptability Mega Lucario Bullet Punch vs. 252 HP / 132 Def Nidoking: 102-120 (27.8 - 32.7%) -- guaranteed 4HKO
0 SpA Sheer Force Nidoking Earth Power vs. 0 HP / 4 SpD Mega Lucario: 294-348 (104.6 - 123.8%) -- guaranteed OHKO
For fun I made a scarf set that can switch in on what most MLuc's would run and OHKO back with Nidoking. If you really try, you can make a lot of mons work in this regard like Staraptor or Victini. This set isn't meant to be taken seriously as an OU viable Nidoking. It is just something that illustrates the point that there are more possible counters out there the community at large may not be aware of. Some who might actually have merit outside of countering MLuc.
A lot of people in this thread are focusing on how hard it is to safely switch into. I think not enough attention is being paid to the fact that while certainly devastating once it gets that +2, MLuc is not too hard to revenge kill with 70/88/70 defenses and 3 very common weaknesses. Even when it does get that free turn/+2 and killed a mon on a wrong guess it is very stoppable. Special MLuc (or Phys w/o Espeed) can't sweep if they have semi healthy TalonFlame. Any Garchomp you face could be scarfed. Breloom can mach punch you to death from full hp. Greninja outspeeds and KO's with hp fire. Scarf Gene is omnipresent. Trick Room teams make his speed a liability. There are plenty of revenge killers capable of stopping him after he gets going. Lucario's base speed also isn't that great until it evolves successfully, which can be very difficult to do against offensive teams.
Personally I don't want to see him banned and would rather deal with one really powerful mega per team like MLuc than deal with a team of unrestricted mons like gene, thundurus (prankster t-wave hax...), deo-s, etc. I think most good teams deal with MLuc without having any real dedicated counters anyway, but that is just my opinion. I just don't think a ban is necessary at this point in time.