I (same as the other user) thought that Bruce Willis manages to send a message saying that it’s not 12 Monkeys and that’s how they figure out it’s the guy on the plane.
Also, the scientists in the future wait for a message on the answering machine. The message on the machine changes based on what Bruce does in the past so it’s clearly not a perfect loop. Actions in the past influence the future so you’re back to paradoxes.