I don't think this is true (at least not "immediately").
The paper is arguing that we will need computers to help decode any non-trivial message, and any computer program capable of decoding a non-trivial message will be Turing complete, and hence capable of running virus code that could have damaging or destructive effects. (The paper's example was a message containing equations in LaTeX, which is Turing complete, hence an ETI could embed a virus in LaTeX code, and humans might not be able to spot it.)
The strategy the paper is advocating, as far as I can see, is that, unless the message is simple enough that humans can decode it without computer help, and thereby check directly whether it contains any dangerous information, the message should be destroyed. I suppose this could count as "we can't tell whether we can decontaminate it", but I'm not sure that's what you meant.
Edit: If we were incredibly paranoid and had some self-sacrificing astronauts it could be a one-way trip to Mercury.
Just speculating, without knowing how we could get to such a predicament.
2. How would you identify that what you've created is an AI?
3. Under what circumstances would you decide to trust the AI that you've created?
4. Under what circumstances would you be confident to feed a potentially malicious potential AI to your trusted AI?
But more to the point, who knows what it can convince the astronaut to do? Can it convince the astronaut to transmit a hostile message back to Earth, suborning the receiving computer, and thereby letting the AI out of the box?
In the AI alignment field, this is called the "value drift" problem.
I may have been unclear: the astronaut is never intended to leave the box, he burns with the box. The astronaut is paralyzed save for his tapping finger, and on a doomed one way trip.
I think what the paper actually shows is \exists message M, s.t. \forall decontaminating functions F, F does not decontaminate M.
In fact, we know the title (as I interpreted it) is false - the paper gives an example of a message that can be read as plain text which can be truly decontaminated.
Basically, when we get a message, we'll be able to immediately tell whether we can decontaminate it or not. If not, the paper argues we're doomed because eventually it'll leak. I just don't find that to be very interesting, and definitely not as strong a claim as the title (as I interpreted it).