If I have a crew, encounter a contact and gain a new crew to replace the first one, does that first contact token just stay gone, or do I put that token on the planet?

We've been playing that when you replace a crew member, the replaced one just stays gone. But it makes more sense that they'd just hop off on the planet where you ditched them. Especially since their bounty card could still come up.

Page 6 (Crew) and 7 (Discarding) of the RRG. Discarding a crew that has a contact token puts the token on the nearest available planet slot. Likely so that you can't screw over people with Bounties.

Notably though, I believe that this is only for discarded crew cards, and I believe it doesn't apply to things like Black Krrsantan (Who you can potentially fight and discard his contact token, or take him on as crew).