The ork hacks you critically in the common sense with his axe of nondeterminism and the severed part flies off in an arc! You have been struck down!
I'm a big fan of deterministic combat systems. As some have pointed out, the origin of non-deterministic systems were pen&paper RPGs, where all of the dice rolls were clearly visible and actually part of the fun. In most roguelikes, though, they aren't visible anymore. Even worse, some games have adopted complex systems which are extremely hard to understand and - again in contrast to many p&p RPGs - unpredictable if you don't go source-diving. The whole fun of deterministic systems is that you can always predict what's going to happen, which encourages planning ahead and recognizing game-critical moments before they happen.
There's one mechanic, though, that plays an important role in classic and contemporary roguelike games, and that's the concept of a critical hit. ToME4, for example, clearly tells you your chance to crit and offers you many ways of directly improving your crit rate, as well as improving the consequences of such a hit.
The nature of the critical hit system, one might infer, is inherently non-deterministic, and impossible to transfer to a deterministic system. However, I'd like to show a few ways how this mechanic could be adapted to a deterministic system by a developer who cares for it.
Guaranteed Minimum Damage: One (admittedly unclean) possibility would be to set a random crit system on top of a combat system that in itself is deterministic, thus guaranteeing a lower bound of dealt damage. This model treads a fine line between full predictability and full unpredictability, and it is the decision of the developer whether it guarantees enough predictability to be fun.
Critting as action: At a certain point in combat, the player might decide to attempt a critical hit instead of a standard hit. Since the critical hit system here is deterministic, the crit chance must be based on some clearly visible number or formula. This leads to the problem that the player, provided he has access to information about his enemy, will always know whether a crit attempt will succeed. Thus, we must find a way to keep the player from constantly critting the enemy. A nice way to do this would be a combo point model, which at the same time could be used to scale the critical hit in terms of damage. A similar system is used by ToME4's brawler class - the effectiveness of finishing moves is dependent on the generation of combo points generated by combat. The tactical option presented to the player would be the question whether to spend his points on a critical hit or fight on and do a more powerful critical hit later on in the fight. Depending on how much information about the enemy the player knows, this model is more or less fun.
Saving up for a crit: The player might save up his energy for a single, well-aimed strike. This most likely implies the existence of an action like "aim", or in the case of a spellcaster, "charge", which replaces one turn of attacking or moving. These are just examples for how one might present this mechanic to the player. The problem of crits either happening during the entire fight or not at all does not exist in this model. Of course one should take care that saving up energy is only done to a limited degree out of combat, so that the player can't save up for a Quadruple Uber Strike of Greater Doom while hiding cowardly in a corridor far away from the enemy.
Crit depending on enemy status: This is mainly based on the idea of combat consuming a resource, say HP or stamina or armor. Once a certain damage has been done to such a resource, the player might be allowed to land a critical hit instead of a normal hit. The main problem with this model is that it acts much like a body-part model: Once you're past a certain point, you've already lost although you're not completely dead yet. I personally don't think this is a very good approach, but some people might find it interesting.
In summary, I personally think critical hits in deterministic systems work best when they require some effort on the player's side to land. Feel free to disagree and tell me why. :)