what happens to an injured pokemon shuffled back into the deck
If a Pokémon changes zones, The Game essentially loses track of it. If it comes back into play, it is considered a new/different Pokémon, even if both players know it is the same card.
So yes, the damage (as well as all other markers etc.) on it would indeed just vanish.

To back it up with rulings from the official Rulings Compendium on http://compendium.pokegym.net/compendium-bw.html:


  Q. If I use Pokemon Communication to put a Pokemon into my deck, am I
  allowed to voluntarily fail and choose to take no Pokemon out of my
  deck?   
  
  A. The contents of your deck is not public knowledge so the deck
  search can fail, even if you've just put a Pokemon into the deck. (Feb
  4, 2010 PUI Rules Team)
  
  
  
  Q. Can I play Unown onto my bench, activate its "Farewell Letter"
  ability to discard it, and then use Revive to put it back onto the
  bench and use "Farewell Letter" again?  
  
  A. Yes, you can. (Dec 3, 2015
  TPCi Rules Team)