Well, I am
NOT the world's greatest battler, indeed I doubt that I will be among the few hundred folks who have the time and skill to meet the suspect reqs (which were kinda confusing for me, using values from two very different ranking systems and whatnot). However, I would like to weigh in on the issue anyway for all three.
Mega-Lucario:
http://www.smogon.com/forums/threads/portrait-of-an-uber.43566/
fits the offensive characteristic extremely well for reasons debated to death already. No further comment is needed.
Deoxys-S: This one is a toughie, if only because I do not see it terribly often. I find it very vulnerable to pursuit trapping, and while it is near impossible to prevent it from setting up hazards without magic coat / magic bounce, it is fairly easy to stop it from laying down more then one layer without dieing (turn 1: swap in bulky guy that scares it off, turn two, scare it off or else it risks dieing). While it's attacking sets can make for very scary surprises, they are little more then the equivalent of a scarfed Genesect that can change moves but lacks access to u-turn. While being comparable to one of the top OU threats is certainly not bad, it is forced out by pretty much any bulky attacker of which there are plenty. Add in the fact that there is a whole new slew of bulky pokemon with respectable attack and priority, and suddenly you wonder why that overkill speed was all that great in the first place. I'd say OU is fine for the time being.
Genesect: This guy is a toughie. He lacks the raw power of mega kanga, deo-n, mega luca, and even blazekin, but he is phenomenal at creating momentum. After a fair bit of playing last night and much thought, I have decided that he should stay in OU and here's why. Due to the fact that Genesect does not have the raw power to be able to severely dent nearly every pokemon with a single move (hello CC mega lucario), he can be played around. I will take a relatively common battle conditions from my own experience to illustrate this point.
Situation: unknown Genesect vs substall Gliscor, both healthy (for the sake of argument, lets say they are their respective team's leads). Gliscor uses protect to scout out what genesect does. If he uses ice beam, the next decision is simple. The gliscor player suspects that gene is probably now choice locked and is now free to swap to a pokemon that can easily take it, lets use CB ttar. From here, one of two things happen, either the genesect really WAS choice locked and ttar gets an easy kill by pursuit trapping, or it was not, in which case the genesect player has the option of changing his move. However, in doing so so early in the game, the genesect player has allowed his enemy to know that he is in fact not scarfed, greatly
reducing the number of things it can come in and threaten (like the genies for example, every single one of them can threaten gene due to their powerful attacks if they can go first). Since gene does not have a phys boost due to having come in on a gliscor, none of his attacks are likely to kill ttar in one hit, and if any of them do significantly damage him, it will further inform the player of what kind of pokemon can swap in safely against it. If he uses u-turn, pretty much same story, except that now it's gliscor who is at risk (this time almost certainly lethal) instead of ttar, the fact that if gliscor does stay in, he will be dealing with whatever else comes out, and the fact that gliscor has the option of using double protect. Protect gliscor is not obscure or unviable, and yet with a single move and a swap to a very popular gliscor partner, the player either removed genesect from the game for free or gained valuable information on it's moveset at the cost of an injured, but not dead ttar.
You can repeat a similar situation with just about any protect lead and/or phys defensive wobbuffet (replace protect with counter and laugh as you get free kills off of your opponent's genesect)
As for shift gear genesect, not broken, not even a little bit. Espeed is a wonderful move, but with gene's only decent attack, +1 or even +2 is not going to turn this guy into the next arceus or mkahn. His coverage, while by no means bad, isn't absurdly good either, and once he uses shift gear, he only has 3 moves, one of them almost certainly espeed and the other two are torn between iron head, blaze kick, ice beam, and x-scissor. Shift gear literally takes his greatest strength, the ability to have absurd coverage and easily grab momentum, and throws it all away. If you want to e-kill in OU, just use dragonite, or SD pass to an entei, genesect has better things to do.