To sum it up for those not bothered to read back pages, the best counters to Mega-Lucario are: defensive RestTalk Gyarados, Mega-Venusaur, Moltres, Zapdos, and defensive Volcarona. (Defensive implying the offensive variants do not counter it, only check; the others just don't even have viable offensive variants in OU)
As for Luke being too frail to set up, I find that anything that doesn't KO Luke or cripple it with status (special Lukes do not mind burns) while getting OHKOed by +2 Luke is enough for Luke to gear up and start wrecking, and that can include a lot of things, like Rotom-W and Fairies. Heck, something like non-LO Greninja is fair game for Luke to set up. Just ensure Luke kills everything after setting up, and it will punch holes or outright clean house.