on the subject of troll diplomacy, us, them, and the elves all hate the undead, but theres a coordination problem; elves wont work for the trolls, and vice versa. assuming our main goal is not to die horribly, we can potentially act as a go between the two to, at the least, ensure they are more focused on killing scourge than each other.
to that end, i think a good way to head off our immediate troll animosity issues would be with a trade, we give them food in return for their highelf captives. they dont starve, and we get more skilled manpower (or at the least, an in with the local group). additionally, it would be a very good idea to inform them about scourge taint/sabotage of their own food supply. if that situation doesnt improve we might have to take t upon ourselves to root that out by way of subterfuge. right now the more groups arrayed at the scourge, the less they can focus on zerg rushing us; it would ill serve us if they were to weaken at this point in the game (it goes without saying that a fight between us would be an unaffordable waste).
some other matters, i recall from the expanded river patrols turn that there would be an option to investigate the rumors of a paladin in that area. also, i think you forgot to include a follow up for the note found at browman mill.