I actually just did this. This is the mob you want:
https://wiki.project1999.com/Savarixsa_Zexus
She's in the back of the Grobb Shaman guild. She'll give you a letter to deliver to the necklace quest giver. The faction boost is substantial enough that I only had to do it once. I believe it took me from dubious to indifferent on a single turn in.
You will be KOS to the Trolls so you will at the very least need to invis back to her. I had a friendly Bard pull her out to zoneline and charm her so I could easily talk to her and get the letter. Recommend that method if you can get a high level Bard or Enchanter to help you.