I think there is no median level of randomness in a MMO. All random factors can be contributed to the game designer wanting to afflict a particular level of uncertainty in the MMO to players. As to the idea that, for a mission you need to kill X number of creatures to get an item will frustrate players is not the point of MMO. A MMO is designed for you and a group of friends to complete a mission and not meant to be played individually; after all it’s called Massively Multiplayer Online for a reason. Otherwise you could call it a RPG or other types of games designed for individual or a few players.

Randomness in games is designed to increase the probability of different results each time the game is played, like you said. As I said before the game designers wants to in part a level of uncertainty to the mission, in the case of collecting tusks, it would be also quiet boring to kill one boar and get the one tusk as there is no sense of achievement, your farming like a farmer.

One reason the game designer might have made missions like collecting tusk, might be so you will ask other players if they have excess items so you can purchase these items from other players (increasing what I think is the main drive of MMOs, the social aspect of the game, communication between players).
I make I note that I have not commented on your example of Castlevania’s on DS as your question was about MMO.
If I have offended anyone it was not my intention. :)

Actually, it seems to me that you are mixing up two properties, randomness and not-making-sense, and blaming the wrong property for your frustration.

One thing that I find irritating about many games, WoW included, is that "boss"-flavored encounters have important elements which don't make any sense in terms of the rest of the world. Fighting Ed Van Cleef (?) in the Deadmines, his associates spawn as he gets injured. And that makes sense how? And you could anticipate it before the fight how? And it is satisfying, how, to figure out a strategy of killing the adds ASAP so that as VC becomes more injured more you never need to fight too many at once?

To me the main problem with monsters spawning and lurking in cleared paths is similar, that it doesn't make sense, and relatedly that you can't see what's going on or respond to it in any meaningful way.

Is randomness the problem for you, or meaningless incoherence? Is a system where monsters predictably materialize on cleared paths less annoying than one where they materialize randomly on cleared paths?

I think the right way to fix that frustration (while keeping a similar challenge in the great scheme of things) would be not to reduce randomness, but to reduce incoherence. How about a system where monsters wandered somewhat randomly over larger areas than just the path you wanted to use, and where you could see some of what was going on, and do sensible things to evade them? And, ideally, it would make more sense in terms of the game world than random materialization (an ecosystem of monsters at one end, or ghosts-spawn-in-the-graveyard at the other end of the plausibility scale).

Given gameplay involving evading and picking fights and such, I really don't think randomness would make it less interesting. Mobs which react by predictable clockwork can be an OK design choice in some cases, and predictability does avoid various implementation difficulties. But for any challenge involving evading mobs or picking fights with the weakest groupings and/or in the best terrain, a lack of randomness tends to make things pretty dull, especially for replay, and it's not too difficult to implement suitable randomness. I expect to see a lot of aimlessness in a real animal or person searching or wandering, and much less aimlessness in urgent matters like combat. Randomness occurs in combat, too, but random aimlessness seems easy to simulate, while it's hard to simulate intelligent responses to randomness in intensely goal-directed stuff like combat.

I notice that in sneaking-related games I've played (Deus Ex, e.g.) the mobs seldom had much aimless randomness in their motion, and that's perhaps evidence that it's harder than I think to implement it well. But those games didn't have as much replay value as something like Civilization, where many random things determine the way one's enemies happen to be distributed, and then one has lots of information (though not complete information) to use to choose how to deal with it. Replay value is often a consideration, especially now that so many game designers are chasing a subscription gold mine, so I think randomness will often be a good idea.

A perfect RPG, in my opinion, would never have any quest in the form of "Kill X boars", "Kill X more boars", "Collect X items" etc. where X is any number larger than about 5. If you can kill one boar, you can kill them all. It just takes, nay wastes, time. And it gets old. Instead, I'd have quests like "Retrieve item X from dangerous creature Y. Bring friends.", "Kill the boss mob of this group of mobs so they'll stop attacking my farm", etc. Set goals that will be somewhat difficult but don't require unreasonable repetition.

Also, you didn't touch too much on randomness in combat, but that's even harder to balance. In WoW they've been trying to tone down random burst damage ever since launch - people don't remember the 50 times they beat an unbuffed warrior 1v1, but they sure as hell remember that one time that a fully geared warrior came in with the old 40% enrage up, plus battleground berserker buff, plus player buffs and recklessness active... and took their head off in two swings. Combat without an element of randomness becomes boring in PvE, but too much random is bad for PvP.

Some interesting change to random drops was done in WOTLK. Maybe you did not notice it, but if you did not get a quest item drop from a looted mob, the chance to drop on the next mob is increased more and more by the game... I cannot find the source anymore, I think it was Ghostcrawler who dropped this information.

I actually liked it, I never despaired because I did not get the final quest item drop for a long time in WOTLK.

It gets a bit better if there's a concept of "safe" zones and "unsafe" zones, where only the latter spawn monsters randomly. At least here you're informed that you have to be on your toes.

But I still don't like it.