I've killed a fair number of ulthork or walrus in my day. Some for exp, some when I decided I wanted myself an ulthork tunic. So, eventually the day came that I went to cobalt scar, and found the Othmir to be amiable to me. Oh happy day.
But, not much later I discovered where crustacean armor came from. My twink had an itch, and that crusty armor definetly scratched it. Killed over 60 othmir warriors to land myself a nice pile of plat and a full suit of crusty for my alt. Then, while foraging in the wakening lands, I discover a quest that takes an item I foraged there and results in a nice resist necklace. Drat, it involves the othmir and they are now threatening to me! Well, I head to east wastes and start layin' the smack down on the ulthork. Eventually, I'm 8 tusks richer, and dubious to the othmir.
Just to see, I hand in the two sets of tusks. With a charisma of 77, and a faction of about as low as it could possibly be but not be KoS, I recieved as a reward: one ruby, and one blue diamond. The former being mildly good, the latter being arguably the best possible result.
Not a lot of comprehensive research, but proof enough for me that it is simply random and not faction or charisma based.
P.S. I also received a message about being on watch duty and not having time to converse on hail, but the keywords further on still worked. My guess is that /this/ is based on the dubious faction but I cannot be sure.