There is no NPC's from enemy factions spawning within Half-trolls' current sphere of influence, which mostly covers Pertorogwaith.
The closest enemy to Pertorogwaith is the Tauredain, who only spawns in the Jungle. What that means, is that if you have negative alignment with the Half-trolls, there is practically no way way to get positive with them again.
Since they (as far as I know) are the only faction to have that problem, it may be a good idea to change their sphere of influence to for example cover some of the Tauredain Jungle (similar to how Rhûdel has a sphere of influence around Minas Tirith).
For now, I suppose the only option players have is to spawn in an invasion with a horn of conquest, within Half-trolls' sphere of influence.
EDIT: As it turns out, they have a small sphere of influence around Poros, so it's possible to increase the alignment with them, if it's negative. It may still be worth considering having another one in Tauredain, since it is their neighboring enemy, but this does solve the initial problem.