Random rewards suck: Zubon describes the downside of random rewards in a blog post describing how he was unlucky on the roll for a desirable piece of loot 15 times out of 16 attempts even though he had a better than 1 in 6 chance. I have been there, I assume we all have and it is entirely soul destroying to hit a losing streak like that. Having some grasp of basic probability only makes it worse when you realise that after 15 losing rolls you have exactly the same 1 in 6 chance of winning the next roll* as you had on your very first roll. Zubon actually left the game for six months after his losing streak. I think that game developers recognise that randomness can be a great demotivator, in games like WoW and LOTRO we have seen a move towards token rewards rather than random drops as a more predictable means of allocating loot.
Remember how good it felt when a shiny sword dropped from the very first Orc you slew. That random reward felt great and was a great motivator. The truth is that randomness only sucks when you are losing. Winning an unexpected random reward feels great.
It seems to me that it should be very easy to keep fun side of getting random rewards while hiding the downside of demoralising losing streaks. The key lies in the word "unexpected". As long as you are not expecting a reward then you neither know nor care when you lose some behind the scenes random number calculation and don't get one.
The guiding principle is that rewards that players expect should not be random.
Examples of expected rewards are:
Anything required to complete a quest.
Anything that acts as a gate to further content (keys, radiance armour etc).
End of instance rewards such as epic armour sets and epic loot.
In fact anything that comes in a set because someone is going to be stuck looking for the last piece.
Anything needed for character progression
Anything needed to gain an achievement or a title
Rewards that players don't expect can be as random as you like.
Examples: Random world drops, random encounters with special mobs
Of course human nature also comes in to play here and as surely as you create a random world drop someone somewhere will decide that they absolutely have to have it and get annoyed when it doesn't appear after they kill ten thousand mobs. To deal with this scenario I would further suggest that any item which is a genuinely random reward should be saleable to other players. No bind on acquire for random rewards.
(* Probability theory soundly asserts that past outcomes do not affect the future outcome of random events but a certain amount of common sense is required in its real world application. If you roll a dice fifty times and it comes up 6 every time it might be prudent to doubt whether or not that dice is truly random)