I Knew It: Some fans had speculated that Terry and Matt's parents were divorced because the boys both look nothing like their father (they have black hair, compared with Mary who is a redhead and Warren whose hair is light brown - genetically improbable). Flash forward to the Justice League Unlimited episode Epilogue which doubles as a Fully Absorbed Finale, and guess what? CADMUS had Warren's genetic material overwritten with Bruce Wayne's, making him the boys' biological father. According to the series' staff, this decision was a Sure, Why Not? motivated by the realization of said genetic improbability. But fans were wrong about Terry's mom having an affair.
Barbara Gordon was voiced by Stockard Channing in Seasons 1 and 2, but was replaced by Angie Harmon for Return of the Joker and Season 3. This would not be a first for the DCAU Barbara Gordon, as she did undergo this trope twice in her Batgirl days, too.
Queen underwent this, too (having been voiced by Amanda Donohoe in her first appearance, then by Sarah Douglas in her other appearances), as did Paxton Powers (Cary Elwes, then Parker Stevenson), and Jack (Scott Cleverdon, then Nicolas Guest).
Both Zeta and Agent Bennett had different voice actors (Gary Cole and Joe Spano, respectively) in their debut episode than they did on The Zeta Project and their other appearances on Batman Beyond (Diedrich Bader and Kurtwood Smith, again respectively). Also Zeta looked completely different in the episodes after his debut in the Poorly Disguised Pilot that wasn't.
See also Big Time, voiced by Stephen Baldwin in his first appearance and Clancy Brown in his second. Justified mostly because at the time of his second appearance he was a deformed freak and sounded different than when he was normal.
One rejected script had Terry become an item with Maxine after Dana breaks up with him, penned by Alan Burnett.
That rejected script is a doubleWhat Could Have Been, as Bruce Timm's original plan for the episode would have explored Terry and Dana's relationship more and ended with it being strengthened. Timm rejected the episode script after Burnett changed the entire purpose.
Mr. Freeze's role was originally just a one-off gag appearance, where Terry was getting a soda for Bruce and, in an awkward moment, would find Mr. Freeze's head and they'd briefly stare at each other, and then Terry would close the fridge and give the soda to Bruce. This was discarded because it was an insulting and unfitting ending for his character.
One rejected script featured the fully grown son of Superman and Lashina (from their brief affair in the Superman: The Animated Series episode "Legacy"). He has long since deposed Darkseid and become ruler of Apokolips, and now sets his sights on Earth. Lashina warns Earth of the invasion, so Batman teams up with Superman and the Justice League to defend Earth. Superman deals with the guilt of not knowing he had a son.
Early on, in addition to the Jokerz there was consideration for other gangs that paid homage to the classic Batman rogues gallery. This was nixed for being repetitive. One such gang would stand out. Multiple gangs would just seem gimmicky. (Considering what we see in Batman : Arkham City, it may not have been too gmmicky)