Look, sorry, I've got a bit of a complex life. Things don't always happen to me in quite the right order. Gets a bit confusing at times, especially at weddings. I'm rubbish at weddings, especially my own.
Monkeyed with again when Kyon recognizes Future!Mikuru when she accosts him, but she insists on "proving" her identity anyway: by revealing a mole on her breast he didn't know was there. Kyon then completes the Stable Time Loop by pointing it out to Present!Mikuru after the encounter.
In the light novels, Fujiwara appears to have previously met Kyon when Kyon first meets him. Cue a confused look on Kyon's face.
When Redwing, a Titan from the future, saw the present Titans, she recognised her former leader Nightwing. However, the present-day Nightwing hadn't met her yet.
Katherine, aka Kit Bennett, in Children Of Time. When the Doctor, Sherlock Holmes, and Dr. John Watson meet her for the first time, she already knows all three very well. Her words and behavior as they exchange goodbyes at the end of her episode implies that she will never seen Holmes and Watson again. (The story takes place during World War II, so both men would most likely be dead already.)
Both used and averted in The Time Traveller's Wife. Henry is well aware that Clare is meeting him for the first time when he goes back and she's six, and behaves accordingly. Ditto for anyone else he meets on his time travels. The "oh, we haven't met yet" scenario tends to arrive when he meets people he will time-travel to, but hasn't yet—Clare at the beginning of the novel, and Alba right before she's born and at the very end.
The first time Henry meets Clare, she seems to know him. After the initial confusion, he is overjoyed to meet someone from his future.
In Millennium, time-traveler Louise Baltimore tries to keep Bill Smith from unknowingly changing the future by meeting, seducing, and sleeping with him. Unfortunately, the next time Bill encounters Louise, its actually the first time she's ever met him, so she rebuffs his affectionate approach. The fact that during their (to Bill, anyway) second meeting she treats him like a complete stranger confuses Bill just enough to cause the disruption in the time stream Louise was trying to prevent in the first place.
Hexwood opens this way; when young Hume asks Yam if they've met before, Yam happily informs him that yes, yes they have, many times. And they have, kinda. The book's Mind Screw designation in its entry is aptly earned.
And in her third, "The Pandorica Opens"/"The Big Bang", it's earlier again for her, but still not her first meeting. Amy mentions that River warned them about the Pandorica and gets the response "Maybe I did. But I haven't yet. But I will have." She recognises both the Doctor and Amy, but not Rory, although later episodes suggest this was just because he technically didn't exist at this point, and his memory was lost to those close to him. Rory is definitely close to River because he's her father.
In her fourth appearance, "The Impossible Astronaut"/"Day of the Moon", River claims that her and the Doctor's personal timelines are not just out of whack, they're going in completely opposite directions: (nearly) every time the Doctor meets River, it will be earlier still for her, until eventually the last time he meets her will be the first time she meets him. (This can't be entirely true. If it was, comparing diaries would be pointless.) All of which sets up a heartbreakingFirst Kiss / Last Kiss.
The episode "A Good Man Goes To War" makes the timey-wimey-ness fifteen times more confusing with the reveal that River is Amy and Rory's daughter, part time-lord due to being conceived on the TARDIS. This means the Doctor was there the day of her birth, and she's been interacting with parents who don't know who she is for ages.
A heartbreaking example from this episode occurs when Lorna, who joined the army in the hopes of meeting the Doctor again, finally sees him at the end of the episode, while she's dying. He has no idea who she is, but he pretends that he remembers her to provide comfort for her final moments.
And again in The Wedding Of River Song, where the Doctor shouldn't meet River anymore - the last time they met was at her birth, which is her first meeting, therefore his last - but he does. And they get married.
Then, the episode The Angels Take Manhattan, they seem to be roughly in sync, with River now a professor and the Doctor knowing full well who she is and who she is to him. They act very much like a married couple in this episode.
The timelines of The Doctor and River aren't exactly one-to-one forwards/backwards, which makes it even more confusing for the viewer when he or she tries to work out River's life in her order.
In "Smith and Jones", Martha's first encounter with the Doctor consists in him walking up to her, removing his tie and saying "Like so, see?" She later meets him "again" in the hospital, and when she asks him about why he did that, he denies having done so. At the end of the episode, he goes off in the TARDIS and returns with his tie undone, proving to Martha that the TARDIS is a time machine.
In the episode "Blink", Sally Sparrow spends the entire episode receiving messages from The Doctor, who's trapped in 1969. At the end of the episode, she finally finds him but he claims he never met her. Sally then realizes that he hasn't been trapped "yet" and then gives him all the means possible to send the messages, thus creating a Stable Time Loop.
In "The Shakespeare Code", there's this exchange with The Doctor and Queen Elizabeth I.
10th Doctor: Queen Elizabeth the First! Queen Elizabeth: THE DOCTOR! Doctor: What? Queen: My sworn enemy! Doctor: What?! Queen: Off with his head! Doctor: WHAT?! ... Martha: What have you done to upset her? Doctor: How should I know? Haven't even met her yet! That's time travel for you! Still, can't wait to find out!
Answered by an off-hand remark in The End of Time: he marries her (and, it is implied, removes her of the right to go by the title of 'Virgin Queen', wink wink nudge nudge.)
In the old-series story Battlefield, the combatants on both sides of the eponymous battle immediately recognise the Doctor from an earlier visit to their world — much to his confusion, since it's still in his future.
Star Trek: The Next Generation, "Time's Arrow", Captain Picard goes back to 1893 and meets Guinan for her first time. He, of course, will known her for a long time in her future and his past.
Lois and Clark: In "Tempus Fugitive", Clark Kent time travels back to the 60s to help his parents (who don't recognize him) discover and subsequently adopt his infant self.
LOST: Desmond and Daniel manage to meet three times, despite there only being two of them. In "Because You Left," Locke and Ethan meet in the past, with Ethan confused as to how Locke knows his name. Later that episode, Richard warns Locke that next time they see each other, Richard won't recognize Locke, and gives him a compass as proof they know each other.
Spoofed in a Fry & Laurie sketch about time travel, in which Stephen Fry is visited three times in succession by Hugh Laurie as first a time traveler from five minutes into the future, then a time traveler from five minutes into the past, and finally a present-day scientist working on a device that will certainly not cause time travel as a side effect, all of whom claim not to have met him before. After Laurie leaves the third time, Fry remarks to the audience: "I'm sure, logically, something weird should happen now, but I can't work out what."
In Misfits, when Curtis re-winds time to undo the event that ruined his life, he has a few memorable meetings with his "present-day" companions, all of whom have no idea who he is. He realizes this when he bumps into Nathan and makes the mistake of asking him for help, and Nathan is about as rude an unhelpful as it's possible to be (partly because he had no memory of Curtis, and partly because he's a giant jerkass in general). Curtis also gets puked on by a drunk Kelly, and has this exchange with his (soon to-be) girlfriend Alisha:
Alisha: What are you smiling about? What...is it a secret? Curtis: I just changed history - I changed the future. Alisha: Just so you know, yeah, saying weird things like that is a real turn-off.
Madame Eva, a mysterious Vistani elder from the Ravenloft setting, seems freely capable of traveling through time as well as space via the Mists. Another NPC, Jacqueline Montarri, murdered the old woman at their first meeting and was cursed for it; she's since encountered the still-living Madame Eva several times, earlier in her victim's life. A subversion, as Eva knows what fate awaits her due to her fortune-telling powers, and is getting her payback in before it happens, spitefully taunting Jacqueline about her cursed status each time they encounter one another.
In World of Warcraft, when you speak with Chromie, a time-traveling dragon in humanoid form, she says ", good to see you! Or is this the first time that we've met? I'm in so many places and times right now I sometimes have a hard time keeping track of all of it!"
Which is used to justify the fact that you may or may not have met her while leveling up, depending on where you chose to go.
In City of Heroes, Mender Lazarus greets you with familiarity the first time you meet him, talking about all your past adventures, and doesn't recognize you the third time, due to time travel being funny that way.
In the original Bard's Tale III, you meet Hawkslayer early in the game. He remembers you, and gives you the password you gave him a long time ago (from his perspective). Later, you have to give the password back to his younger self to get him to join you then.
In Neverwinter Nights you meet a time traveller who doesn't know if you have met yet and is unsure what they have told you.
In Astro Boy: Omega Factor, Pook is introduced this way. Astro doesn't know him but he later on goes back to the past where Pook is from, thus explaining Pook knowing who he is. In a curious twist, you later go back in time to that "first meeting" and they recognize each other.
In Chrono Triggerthe main characters discover that the Guru of Life trapped on Mt. Woe is actually Melchior, whom they met in the present. Naturally, they recognize him but not vice versa. Curiously, the Melchior in the present era never gave any indication that he already knew them beforehand...
Because in the original timeline Melchior was never imprisoned on Mt. Woe. Until Crono & co accidentally sent Magus back to the Dark Ages, Melcior really had never met Crono until the Present Age. Time travel is confusing.
Twice in Ōkamiden, with the same characters. When Nanami the mermaid first meets Chibiterasu in Agata forest, she greets him as an old friend, but Chibi acts all confused and does not seem to remember her. This is explained later in the game when Chibi travels nine months into the past and meets Nanami again, and he greets her like a friend but she does not remember him, because for her that was the first time they met.
Homestuck has the trolls, who contact the kids at seemingly random points in their timeline. This leads to some incredibly weird conversations.
Karkat, upon having a disastrously embarrassing first conversation with John, resolved to progress linearly backwards through John's timeline, which is hardly less confusing than the random method.
The most tragic example turns out to be Gamzee. When he randomly contacts Dave, the latter remembers the "oblivious juggalo" troll and innocuously sends him an ICP video. Said video contributes to Gamzee going Ax-Crazy and after comitting some horrifying actions and setting other disastrous events into motion, he contacts a younger Dave, the meeting he later remembers, closing the Stable Time Loop.
Ben 10: Alien Force has the aptly-named Paradox, who already knows Ben quite well when they (from Ben's perspective) meet for the first time, due to them working together several times in the future.
Paradox: "Swampfire, that takes me back. Or is it forward? It's so hard to tell, isn't it, Ben? Have we met yet?"
A Running Gag of sorts with the above quote is that every time Paradox appears in an episode, Ben will use Swampfire at some point.
An episode of Gargoyles has Goliath running into the London clan. Though he swears he's never met them before, they certainly remember him, and blame him for the death of Griff, one of their members, during The Blitz. Seeking to figure things out and clear his name with the Londoners, Goliath heads back in time, and repeatedly saves Griff's life. After several close calls, Goliath decides history apparently wants Griff dead, so sidesteps fate by pulling him into the future with him, closing the time loop.
In X-Men, this was the source of some hilarity in the first time-travel episode. Bishop meets Wolverine for the first time in the Bad Future, and then he travels back to the past (or rather, the normal Present-time of the series) to Set Right What Once Went Wrong. Upon meeting the Wolverine of that time period, Bishop is somehow surprised that Wolvie doesn't remember him.
Taking into account the general flexibility of the Marvel universe and timeline in general, plus the fact that Bishop is a time traveler, he might have met him in the past before, and didn't realize this time was prior to that time. Or being Wolverine, he was screwing with him.