I believe it was the first time, except possibly when he introduced himself to Khan during Space Seed.![]()

I watched The Wrath of Khan today for the first time, and I don't find it too hard to believe that they were familiar with one another.
In Space Seed, Khan read pretty much read everything the computer had to offer. If I remember correctly, he even learned about people's ranks and identities and so on. So it isn't too hard to believe that Khan (with his superior intellect and probably superior memory) would remember Chekov's name.
As for Chekov remembering Khan ...
Maybe it is standard for all crew members to be educated on the previous near-death-experiences of the Enterprise, to be better prepared in the event that a similar situation arises.
But Chekov did seem to react in a way that would imply that he directly witnessed Khan in Space Seed 15 years prior.
Oh well. Very funny joke though
