There is a great article on unpredictability over here. This is my opinion on the matter.
It is important to understand the difference between random numbers in the game mechanics and unpredictability. The difference is: random numbers in the game mechanics are a tool to create unpredictability - but they are not the only tool. Unpredictability can come from various sources.
For example, in a WoW boss fight, you never know whether Bob manages to get out of the fire in time. And this is also true if Bob is not a bot, who depends on random numbers, but if Bob is human.
In fact, you don't even need Bob to have unpredictability. If you don't know whether you yourself will be able to get out of the fire in time, there's also unpredictability and thus tension. If you knew exactly what is going to happen, WoW – or any game- wouldn't be fun at all.
Consequently, the interesting question really is not whether games should be unpredictable – they need to be. The important question rather is where the unpredictability comes from (and how much you need).
The problem with random numbers in the game mechanics as a way to create unpredictability is that humans tend to question why things happen – especially why bad things happen. One way to stop players from asking this is immersion. As long as the player is immersed in the simulation part of the game, everything's fine. His soldiers miss, they die, he may even lose the game. Maybe he had never had a chance due to a bad random seed. Maybe he played too risky. It doesn't matter because he enjoys being the commander of a squad and accepts that bad things can happen in the field. That's the way it is in real life. No military plan survives the first contact with the enemy. The trick of being a good commander is not making a plan that works if everything happens as planned, but to make a plan that works even if everything goes wrong - while also taking advantage if some things don't go wrong or even work out exceptionally well.
Unfortunately, if the player is not immersed in the simulation and only concentrates on winning the abstract game, randomness in the game mechanics can be very unfun. When playing a game like X-Com, many players don't usually think about what would happen if the 80% shot misses. Instead, they assume that everything probable works and if it doesn't they reload. As a consequence they miss a great simulation that actually has some tension and climaxes - and not just a straight way to victory (what most computer games tend to be). By accepting defeat the gameplay mechanics can actually create a story that is fun to be experience.
For example, yesterday I continued my UFO ironman-classic game. I had a mission where my five soldiers suddenly faced about 8 enemies. The problem was that my two snipers missed five shots in a row – each of them having 70%+ probability of hitting. I ended up fleeing the battlefield with only one sniper alive.
On the next mission I had only one sniper and 4 rookies. Due to bad luck and reckless tactics the four rookies died very soon, too, but this time I decided to fight it out and miraculously the sniper, who had just fled the last mission started to hit with every shot while also managing to not be hit by the enemies. A few turns later he had eliminated every enemy on his own. Randomness cuts both ways. In this case it created a memorable story– usually a good criterion for how much fun a game is.
Thus, my preliminary conclusion is: random numbers in the gameplay mechanics are a viable tool to create unpredictability if the player accepts them. One way to make him accept them is to immerse him in a simulation. By immersing a player into a simulation you can also make him accept defeat (bad random numbers) and accepting defeat is essential if you want your gameplay mechanics to create an interesting story.
Unfortunately, most hardcore players and game developers don't care about immersion and gameplay mechanics that create a story, and rather turn their game into a bad movie with funny abstract minigames between the cut scenes. For those games, randomness in the game mechanics can be terrible. Players automatically reload any 80%+ shot that didn't hit and try again. If they cannot reload they blame the random numbers, instead of themselves for not having had a plan B.
To circumvent this problem in games, the randomness can be removed from the game mechanics and be hidden where it is more acceptable: inside the opponent. The gameplay then only serves to multiply the existing randomness into a myriad of possible and reasonable options which result in unpredictability.
Chess does it this way and, to a degree, Counter Strike does. The gigantic number of possible and reasonable actions at every point in time, in combination with the randomness in the opponent's head, create a near infinite number of games. Thus, chess or Counter Strike are unpredictable, even though there is no (or little) randomness in the gameplay mechanics.
The point is: randomness in your opponent's head – or even his skill/execution - is acceptable: After having died in Counter Strike, you could say that what you did would have made you win 90% of the time, because your opponent doesn't usually hit your head at 200 meters with a pistol. But while lucky opponents might be annoying they are always acceptable (“He's just good”). If the randomness had been hidden in the gameplay mechanics (your opponent shoots, the computer throws dice to determine whether it hits your head) it had been much less acceptable.
Funnily, chess computers use random numbers to be unpredictable, but since they are supposed to emulate humans it feels perfectly acceptable to lose to them. The player differentiates between the opponent and the gameplay, and when facing a chess computer they differentiate between the game mechanics and the AI opponent.
Could X-COM be turned into a game without random numbers in the mechanics? Of course it could. You could make all soldiers always miss if the enemy is fully behind a wall, you could make them always hit if the enemy is protected partly by a wall and you could make them always do criticals if they flank the enemy. You could remove all random numbers from the game mechanics and instead put them into the way the computer enemy acts. This might still be a very interesting game.
(Interestingly, the developers have removed randomness from the enemy's actions when compared to old games: enemies now spawn in groups at pretty predictable locations. Not a good design decision, in my opinion.)
Developers often put the randomness in the gameplay mechanics and not in the opponent for two reasons. First, it is often the easier way to make the game unpredictable enough to be fun. And second, from a simulation point of view it simply doesn't make sense that you, as the commander, know whether your soldiers will hit.
The rule of thumb for the developers is this: if you put randomness into the game mechanics, make it acceptable by emphasizing the simulation aspect of the game. If your game does not put a strong emphasis on the simulation try to hide the randomness inside the opponents' actions.
Alternatively, sell your game as gambling (annoying as hell but still fun because the players accept the randomness as central to the game.)