I think I played this incorrectly the first time I tried Redhorn Gate -- When I traveled to the Dimrill Stair, I properly reshuffled two locations back into the encounter deck and reduced my threat by 11 -- I then sorted through the encounter deck, found 3 copies of Freezing Cold, discarded them, and reshuffled.... but in retrospect that didn't seem right to me. The second time I played RG, when I traveled to the Dimrill Stair, I only discarded the one copy of Freezing cold that was already in play and attached to a hero. Thus, I left the other copies in the encounter deck. I think the latter is correct but can anyone confirm for me? Thanks!

Dimrill Stair:: Travel: Reshuffle all locations in the discard pile and victory display back into the encounter deck. If you reshuffled at least two locations, reduce each player's threat by 11 and discard all copies of Freezing Cold from play.

So, it says to discard the ones in play. The ones currently in the encounter deck are not in play, the ones currently attached to your characters are. As such, your second handling was correct.