There are already a non-random systems in parallel (badges, crafting, PVP points) which are useful to varying degrees.

You can have the appearance of randomness without being completely random - it is a piece of software, not a coin flip. This goes double for collection quests. A simple method would be to use the number of kills against a mob type in the drop probability formula. The catch is that you have to deal with loot tables - you don't want something that drops 30 different items to start dropping the whole table at once just because it's seen by someone that's killed it 100 times.