Gave it another try and achieved 38, too. I think there are only theoretical chances of getting much better.
Heroes: Aragorn, Imrahil, Gloin
Starthand: Sneak Attack, Gandalf, Valiant Sacrifice, Snowbourn Scout, Celebrians Stone, Dunedain Watcher
TURN 1
Resource Phase:1,1,1
Draw:Guard of the Citadel
Planning Phase: Celebrians Stone
Quest Phase: Sneak Attacking Gandalf ( kill spider) Aragorn, Imrahil and Gloin quest.
Encounter: Forest Gate, 12 Will against 3 Threat.....Stage 1 done.
Travel Phase: Forest Gate ( draw Sneak Attack, Ever Vigilant)
Encounter Phase:
Combat Phase:
Refresh Phase:
Threat: 33
TURN 2
Resource Phase:1,1,1
Draw: For Gondor
Planning Phase: Snowbourn Scout
Quest Phase: Aragorn ( ready him), Imrahil and Gloin Quest.
Encounter: Old Forest Road ( puhhhh, lucky), 8 Will Against 2 Threat....location and Stage 2 done.
Continue to 3B-Don´t leave the Path-.
Travel Phase: Old Forest Road ( ready Gloin)
Encounter Phase: Engage Ungoliant´s Spawn
Combat Phase: Sneak Attack on Gandalf ( lower Threat), Snowbourn gets killed, Imrahil gets ready. Aragorn, Imrahil, Gloin and Gandalf kill the Spider.
Final Threat 28, no Wounds, 1 Turn.
Final Score: 38
Wow, that was close. And after about 15 tries.