What about an AI that can micro perfectly seems so implausible to you?

Because an AI won't be able to micro perfectly. Where micro perfectly means consistently make the best possible decisions in hindsight at the micro level given the current situation for all possible situations and player skill levels such that it also propagates to perfect macro play. If it is not doing that then it is imperfect. It must also be unexploitable and must provably settle at Nash Equilibrium against other perfect players.

Also,
You say that machine learning is only good at learning is only good at learning local optima. This is strictly not well defined. Local optima of what? classification is done by searching for a good function, treating it as finding an optimum for the data is not really true unless you consider each classifier as optimizing on a space of functions - which is a reasonable consideration (Gaussian processes are an interesting take on this). Some algorithms are specially crafted to optimize on a convex function with only a global optimum, in fact each algorithm will transform the same data into a different space and learn a different function. Some will learn local optimums with respect to the given data in this transformed space while others will learn globals, but their concept of global and local is not strictly meaningful with respect to the concepts the data represents. They are just trying to minimize some loss function. But back to optimizing on a function space for the data - the space or inputs and actions in consideration is often so large, unstable and complex that looking for a global is not even meaningful and impossible if you are thinking of one function for any dataset (game + differing players = different spaces). Even humans cant do this. The No Free Lunch theorem ensures that you cant just throw some algorithm at arbitrary data and expect it to do well for any given dataset. For some it will do worse than random.

As for an AI that can beat the player using the same rules (same rates, no farsight, no buffs) this is not at all easy. You are right in that for a game like rock,paper, scissors a dead simple algorithm like weighted majority will destroy a human but doing well in a more nuanced game is very, very hard. Doing it in a way that is creative and bordering on weird is not hard. Use a mixed strategy and balance exploration and exploitation, penalize overexploitation and decaying memory should get you that far. But doing it in a way that is not completely idiotic and cannot be trounced by the intuition and higher level nuanced reason of a expert human is very hard. I am working on this as a hobby And I can tell you that making a bot play as well as a good human despite having perfect memory,excellent micromanagement,even temperment, and superhuman calculating ability is very hard. I've had to put many hours of thought to come up with something half decent and profitable against mid-weak level players.

Unless you think No limit holdem is harder than an RTS such as starcraft 2.

I'm prepared to be wrong, but I'm not yet convinced. Give me a scenario where a human decision can outplay a perfectly operated AI.

Your assumption is that the AI controls individual units perfectly (in some sense), but you must make more assumptions about the AI! Playing the game involves choosing which units / buildings to produce as well as when to produce them. Those decisions are critical, and therefore the AI's ability to do them is as well, so you need to make assumptions about the decision making ability of the AI. If it is nonexistent, that is if the AI does the exact same build order every game, then the AI will lose. The reason for that is that some units are designed to kill other units and there are a lot of situations that you simply can't micro against. There are many ways to hold units in place, and in a lot of cases the unit AI will control your units optimally (chasing and surrounding other units for example).

But, you just asked for any situation and then I can just say let the AI play Zerg in SC2. In the current state of the game Zerg is considered to be a very reactive race. They have very few offensive options early on, so they must play the role of the defender, but there is no universal defence strategy and in order to survive the player needs to rely on good decision making, which is why it is considered to be the hardest race to play. Their design differs a lot from the other two races in the game in that you build both workers and attacking units from the same source (larvae). That means that if you are tricked into making attacking units and the attack doesn't come, then you will be crushed by an attack a few minutes later because you had so many less workers (trust me, the difference will be greater than any micro can overcome, especially since early game Zerg units don't benefit much from micro). If you don't make enough attacking units then you can easily get crushed by an attack, and a human player will react to what you do! If you don't have a strong defence he will be prompted to attack.

The AI will need to have the ability to adapt, but then you're getting into something much less trivial than unit control, which is my point =)