What is done with discarded Tides of Battle cards?
The FAQ indicates the cards should be reshuffled each combat, as you have been doing:


  Reshuffling the Tides of Battle deck: Immediately before the "Choose
  and Reveal House Cards" step of every combat, all Tides of Battle
  cards are reshuffled together to form a new deck.