It depends on the game.
- Randomized Damage: This tends to work better for games that are designed to be quick, casual, and/or have little to no death penalty. In addition, Randomized Damage can work well (as someone said before) in situations where a player has ample time, resources, and options to re-evaluate his/her strategy in light of some good or bad rolls.
- Deterministic Damage: Tends to work better for ultra competitive games (like starcraft), and games where the player has enough on the line that losing on a failed die roll will piss him/her off enough that he/she might not want to keep playing.
In both cases, its important to balance appropriately. A poorly balanced game with randomized damage can come off as completely random such that player choices have no value. Conversely, deterministic damage can end up boring because everything ends up working out the same way every time. As the game designer its your job to address those concerns in some alternate way.
EDIT: I should add... all good damage models have variance... its just a matter of where you put it and how much direct input the player has on it. In starcraft, the variance comes into play in terms of damage types and the ability of a player to micro-manage his units such that they perform optimally. When two armies clash in starcraft, you can have radically different outcomes based on positioning and micromanagement from one battle to the next. That is not to say that system is better or worse its a matter of preference, and the type of game you're trying to create.