When I finally watched La Jetée, I noticed that film includes a near replication of the scene with the tree trunk in Vertigo: Thus, the scene in 12 Monkeys where James Cole and Kathryn Railly are in a theater watching that same part of Vertigo is referencing both Vertigo itself and La Jetee.
When James tells Dr. Railly she's the woman in his dream, she tells him, quite logically, that she's become the woman in the dream now that he's fixated on her. He insists that it was always her, but he didn't have a name to call her before. This is all well and good until you realise - maybe she's right. Did James only started dreaming of her because he fixated on her, the same way the man who knocked him over became Jeffrey Goines? Or, did she become the woman in the dream because he altered the course of time by kidnapping her, and prevent Goines from being the spreader of the virus through his own blind, Butterfly-Effect actions? Or, was it both at the same time?
Furthermore, did Kathryn only start to feel attracted to James because his presence was altering history so that she could be that woman? Does that explain why she whispers "I feel I've always known you" to him in the cinema?
Before sending him back in time again, the scientist played by actor Simon Jones tells Cole that his idea of preserving the spider was a good one, and to try it again. Jones would know; as Arthur Dent, in the original radio series of The Hitchhiker's Guide to the Galaxy, he and Ford Prefect pulled off a pretty similar trick with a fossilised towel...
It's been 30 years, and the humans still have to suit up to leave home. That means the virus either spores like anthrax, or has some form of animal reservoir. Neither makes sense for a viral/biological weapon; you'd think the side making it wouldn't want it around too long.
They repeat over and over through the movie that You Can't Fight Fate. Why, then, do the future scientists send Jose back at the end to give Cole a gun to attempt to shoot crazy apocalypse guy? Specifically because they knew he'd fail. He fails, he's always failed, he will always fail. Cole had ripped his teeth out and could therefore no longer be controlled by the future, they were only ensuring the Stable Time Loop would occur while getting rid of a pesky loose end. Jones took a plane from that airport that day, she probably would have been aware of the shooting.
At numerous times, James Cole seems to be familiar to lost homeless people, including the wheezy toothless man and the street preacher who interrupts his own recitation of The Revelation of John to cry "Why, you're one of us!" as James passes. This takes on an awful meaning when you recall that James wasn't the first to be sent back in time for information, and that he was singled out for his excellent memory. Who knows how many poor souls they tried before? How many of them wandered the streets of 1990s-era San Francisco, only able to communicate what was coming through an alcoholic haze and ineffectual Bible recitations?