In a story I'm writing, there's a villain who is a genius strategist that can get anything he wants, whatever it is, by developing perfect strategies that can have only two possible outcomes: 1, success, or 2, success. His plans never fail because he always has a plan B, and each plan B has a plan B, always thinking of all possibilities and things that can ruin his plan and coming with a solution to each one of them. If that's not enough, he's also a powerful, almost invincible fighter, heir of two special abilities. Oh, and he also becomes immortal (though he can get killed in a specific, story way), and is an emperor.
In the end he is defeated by a flaw in his logic and a detail he didn't think about in one of his strategies (and by brute force too).
But sometimes you have the impression that he (the villain) is cheating, as he always figures out stuff and is always a step ahead and ends up winning, with no one able to defeat him in whatever way (except in the ending, along with specific story reasons), no matter what the heroes do, as if he is that invincible because the writer is "helping" him to achieve/win, and thus breaking the suspension of disbelief.
So how can I make it so that this quasi-invincibility or "Marty Stu-ness" is something to be amazed at, instead of something that breaks suspension of disbelief (besides justifying)?