When a treasure is recovered do you remove those treasure cards from the deck?
No.


  When you capture a treasure, discard cards to the Treasure discard pile and move the
  figurine in front of you. 


This is also where encountered Waters Rise! cards are placed.


  Discard the Waters Rise! card to the Treasure discard pile.