You're overgeneralizing things a bit. Unless both players are capable of reading each other's minds and also have every single possible result of every single possible move and set combination not only memorized but recallable at any moment, even Chess has a tiny to middling bit of luck in it.
In chess, you may get lucky if your opponent makes a mistake, which allows you to win the game. In pokemon, is it you making a mistake when a critical hit takes out a key pokemon, that wouldn't of been KO'd otherwise? Is it you making a mistake if you make the right switch into an Ice attack and you get frozen? Obviously not.
The other problem is that, the more you remove from the game, the less you're playing Pokémon and the more you're playing "Shoddybattle Online Monster Fight Simulator."
How are we not playing the game simply by adding an additional ruleset to it?
There's also the fact that a lot of players overreact to the "problems" caused by the "luck moves." Case in point, if I use Double Team, the opponent has to miss me (x+1) times for it to pay off (where x is the number of times I've used Double Team). Otherwise, I wasted the turn spent using it. If the opponent misses me once per usage, we're still stuck on neutral grounds as if I never used the move. Let's not forget the fact that I have to sacrifice a moveslot in a game where 4 isn't nearly enough as it is.
On certain pokemon, evasion moves aren't worth using because of the "4 moveslot syndrome" that you mentioned. However, there are many pokemon that are happy to sit there and boost evasion. And it's not frail, powerful pokemon that I'm afraid of here. It's pokemon like Suicune, Cresselia, and other bulky pokemon that can actually take the attack when they get hit, and recover off the damage. Using something like Double Team on Lucario, where you aren't very likely to get more than maybe 2 DT's isn't the smarest. But when you can max your evasion, and have plenty of defense leftover to tank those hits that get through, why wouldn't you?
On that note, if I use Close Combat, I will kill Blissey 100% of the time. If I use Fissure, I will kill Blissey 30% of the time. Which one is more powerful in this case? What are we so afraid of? Keep in mind, I have to sacrifice a moveslot to use something that has only a CHANCE of killing the opponent. Just the same, using something like a Quick Claw is effectively like holding nothing at all 75% of the time.
If you had read the topic on OHKO's in Policy Review, or had any common sense for that matter, you would know that using a OHKO on something that all ready has a ton of OHKO power is stupid. But what about pokemon like Gliscor? Gliscor can switch in and effectivly shut down many physically based pokemon. When those pokemon switch, Gliscor gets a FREE turn to OHKO your incoming pokemon 30% of the time.
So, my first major point is that the moves in question aren't overpowered in any way, they're in fact quite underpowered. Does the problem lie in "Bad" players beating "Good" players by virtue of using these moves when they don't "deserve" the victory? Well, why don't we ban Garchomp, Gengar, and Celebi, because I'm more than certain they've mindlessly let unskilled people win more than their fair share? Is the problem the fact that the moves are THAT bad that we shouldn't even be handing out the option of using them? Well, why don't we ban Magikarp, Caterpie, and Unown in that case? They're not good at all, and nobody should be allowed to win using them by that logic.
So now OHKO moves, and evasion boosters are terrible attacks? Bad enough to be put on the same level as Caterpie and Magikarp? But think, what benefit do you get by using Caterpie and Magikarp successfully? None. What do you gain by landing a OHKO, or boosting your evasion enough so that your opponent's chances of hitting you are slim to none? You gain a game changing advantage based purely on luck.
The second point is that there are ways of managing each of these things that we're overlooking. How many Skarm or Forry players do we have, here? How many of them are actually using the abilities the designers have granted them? Oh, hey, what do you know, they're unable to be killed by OHKO moves, that's very helpful. Too bad they basically have no ability in today's game.
Yes, I agree that Forretress and Skarmory's abilitys are pretty usless right now. But I don't see "giving Forretress and Skarmory's ability a use" as an actual reason to unban OHKO's, considering that they're all ready incredible pokemon.