The problem is that if something arrives at B before B sees it leave A, then there is a way to arrange for a message to be sent from B to A, and a response back from A to B, such that the response arrives before the message was sent.
This is a consequence of special relativity, which allows any spacelike vector to be transformed into any spacelike vector (and any timelike into any other timelike) by a subluminal (less than light speed) change in observer velocity. If you can do any spacelike (FTL) transmission of data, then you can do every spacelike transmission of data if you care to go through the trouble (which is not to say it would be easy, just that physics doesn't prohibit it). Combining spacelike vectors lets you move back in time, so causality is screwed beyond belief.
No, you're changing your terms in that sentence. If something arrives at B before B sees it leave A, it doesn't imply it hasn't left A. B could send a response that similarly goes faster than B sees, and the whole system could end up with A receiving a response from B before A sees B receive the original message. B still sent the message after A sent theirs.
That's not a paradox, that's just faster communication than sight. Similar to how two people can jog towards each other, and receive a response before they reach the other person, much less reach each other's starting points.
---
As I have in another reply in this main thread, I understand that this is what special relativity says. But I also thought special relativity says it's impossible to travel faster than light, so is anything outside what it claims is possible even within its rule-set? How does special relativity apply to the apparently-contradictory world of quantum behavior? Even Einstein didn't think quantum mechanics was correct and didn't fit with relativity, but we deal with quantum behavior on a daily basis, so it's very definitely real.
edit: perhaps more clearly:
Special relativity claims that anything faster than c goes back in time. (I think/thought) it also claims anything faster than c is impossible. But it's an easy thought-exercise to cause instantaneous transmission without causing a paradox, an easy solution being things happening faster than sound not causing paradoxes. Just because you haven't heard it doesn't imply it hasn't happened yet.
It's a subtle point, and it's very difficult to explain in layman's terms. On the other hand, it's very easy to explain once you know how to draw and interpret a Minkowski diagram.
But basically, special relativity means that if you can travel faster than the speed of light then you can travel back in time. An explanation of why that's shorter than a full explanation of special relativity will seem unsatisfying.
So instead of reading handwavey explanations on the internet recommend going out and properly learning special relativity from a textbook. (D'Inverno is pretty good, though it's only one among many.)
A philosophy lecturer of mine said that nobody should be allowed to graduate university unless they understand (a) relativity, (b) quantum mechanics and (c) Gödel's theorem, and I'm inclined to agree. You just can't consider yourself educated in the 21st century without a basic grounding in the important advances of the 20th.
The first level of impossible is that you can't accelerate a body past c no matter how hard you try since continued acceleration will just get it arbitrarily close to c (in every reference frame). The second level of impossibility is that if you did find a magical way to do that then you'd wind up with time travel.
Granted, it's not impossible by that proof because we have faster means of communication (you can detect something before its sound reaches you) (or maybe because it's slower than light), but that's not a problem with faster-than-light communication either. By hypothetically accepting that there's a FTL communication method, didn't you just accept that there's something faster than light?
Wouldn't that imply there's something we don't know about time dilation (if FTL comm is achieved), given that it defines such a thing as impossible? It's a circular argument, it's impossible by this proof because this proof relies on it being impossible. So arguing a hypothesis which rejects that requirement with this proof is ignoring the hypothetical universe that was constructed, and it's not a proof at all.