Arkham Asylum: Living Hell: All the new Arkham inmates introduced in this story (Doodlebug, Jane Doe, Death Rattle, etc.) are treated like they've always been there.
When first introduced back in the 1970s, Lucius Fox had two children: a son named Tim and a daughter named Tiffany. That was it for decades, until a second daughter, Tam, was suddenly introduced out of nowhere in 2002, with Bruce already knowing her and the two apparently having a friendly relationship. Then, following Flashpoint, a FOURTH Fox child, Luke, was introduced as the second Batwing.
Pre-Crisis continuity made Chief O'Hara from the 1960s television series a Canon Immigrant and gave him a counterpart on both Earth-One and Earth-Two. Both versions of the character treated O'Hara as if he had been an established ally of Batman from the start in spite of being created for the 1966 TV show, with his Earth-Two incarnation being more notable in that regard due to not appearing until nearly a decade after the show ended production and Earth-Two being the designated reality of the Golden Age Batman comics, which were obviously printed long before the television show existed. Another interpretation of him would later appear Post-Crisis in Jeph Loeb's Batman: Dark Victory, where he is established to have been killed early in Batman's career as a victim of the Hangman murders in spite of not even being alluded to in the preceding Post-Crisis stories.
Jeph Loeb introduced a new character called Thomas Elliot in Batman: Hush. He was apparently a childhood friend of Bruce's, and Bruce holds him in incredibly high regard, and it's heavily implied that Thomas partly inspired Bruce's methods as Batman... Which is why we never heard of him before the story arc. This was (almost) an exact copy of a Superman story just a few years before. During Zero Hour: Crisis in Time!, we were introduced to Kenny Braverman. Childhood Friends with the hero — check. Been here all along — check. Becomes a Big Bad (Conduit) — check. Drives our hero to the brink of madness — check. Tries to kill our hero — check.
Batman (Chip Zdarsky): Turns out Oswald Cobblepot had managed to father several children. Only one of them, Ethan Cobblepot, was actually known before this run.
Batman (James Tynion IV): In the aftermath of the The Joker War, writers introduced Ghost-Maker, a rival vigilante operating out of southeast Asia that trained with Bruce when he was travelling around the world and building up his skillset. The justification for him never being mentioned was that he and Bruce had a falling out when they were younger over Bruce's motivation for fighting crime, as Ghost-Maker views crimefighting as an art as opposed to a duty, and they eventually came to an agreement that Ghost-Maker would stay out of Gotham and Batman would stay out of any place Ghost-Maker set up shop in.
When the first incarnation of Copperhead debuted, Commissioner Gordon explained that Batman had already been foiled by him many times in the recent past, though the reader wasn't made privy to any of those previous attempts to nab him.
Subverted with the original Red Hood, who Batman described as a villain from early in his career who vanished without being caught. When the Red Hood returns, it is revealed that he was actually the Joker, a Canon Character All Along.
Batman Odyssey: Throughout the story, new characters show up with no introduction, and everybody just acts like they've always been there. The most blatant examples have to be Sylvester the jive-talking beatnik wizard, and the Roc, which had apparently been terrorizing Jamroth Bok's people for years before Batman blew it up.
The Long Halloween: When the supervillains of the story gather in Falcone's office in the final chapter, the Penguin—who hasn't appeared in the plot at all—is part of the group, although he doesn't get any lines. Penguin would get more attention in Dark Victory, so presumably this was an Early-Bird Cameo (tee hee).
Katarina Armstrong, the second Spy Smasher introduced late into the first volume of Birds of Prey, was a college roommate and rival of Barbara Gordon's. She had never been referred to before that.
Munira Khairuddin, AKA Obscura, debuted more than halfway through Batgirl (2011) and was also established as a former college classmate and rival, despite never having been mentioned prior.
Deconstruction this; towards the end of the run, Barbara lets her childhood friend Greg crash at her place. Babs' friends point out that they'd never even heard of him until this point, and eventually it's revealed why: Greg isn't her friend at all—he's a criminal that Barbara took down years ago who got his hands on memory altering technology and began a campaign of gaslighting and criminal enterprising to destroy her life, starting by inserting himself into her memories.
Frankie Charles, who made her first appearance in the Burnside era of Batgirl (2011), had been an acquaintance Babs knew from her time in physiotherapy.
In the first issue of Batgirl (Rebirth), Barbara happens to run into a man named Kai, a childhood friend of hers who, once again, had not been seen or referred to prior.
Batwoman: Variant. The character has been around since 2006, but didn't have any real ties to Batman, even after it was revealed in a later story that they were cousins. Suddenly, Detective Comics (Rebirth) establishes that Kate and Bruce were quite close when they were children, and that Kate even comforted Bruce at his parents' funeral.
Robin (1993): Dodge puts together a group of villains who all hold heavy grudges against Robin for his revenge plot against Robin but of them only Dodge and Tapeworm had ever appeared before.
Red Robin: Z, a member of the League of Assassins assigned to aid Tim, was one of many hooded ninjas who fought Batman and Robin during the process of Ra's al Ghul's resurrection.
Tim Drake: Robin: Darcy Thomas (Sparrow) wasn't part of the original We Are Robin characters, she was introduced in DC Future State as a former member and friend of Tim's, and got backported into the normal timeline.
Alternate Universe
Batman '66: The "Lost Episode" one-shot, adapted from an unproduced episode treatment for the original television series written by Harlan Ellison, regards Two-Face as if he had been a recurring foe of Batman and Robin in spite of the fact that he never appeared in the 1966 show nor in any issues of the main comic tie-in.
The Batman Adventures: Throughout the DC Animated Universe's entire run, Jason Todd was never implied to have existed in the continuity and Tim Drake was always made out to be the second Robin, being a bit of a Composite Character with traits of both Jason and Comic Tim Drake, up to and including his own version of A Death In The Family in Batman Beyond: Return of the Joker. The Adventures Continue finally establishes Jason Todd as being the second Robin that Batman never talked about out of shame.
