Do you shuffle the already played cards back into the deck when using the 'Winter Is Coming' card?
It makes sense that you would put the discard pile back into the deck and re-shuffle - this is what we have always done in our games. This obviously means that you can have the reappearance of cards that have already been drawn once before.

It wouldn't make sense to just shuffle the remaining cards - what would be the difference between that and not shuffling the remaining cards? They're still unknown and already/still in a random order.