In regards to Chekov showing up in season 2, it gets even more confusing with continuity when you fast forward to the movies and Wrath of Khan. Khan tells Chekov that he "never forgets a face", but Khan actually never met Chekov in the episode "Space Seed" as he had not yet been cast for the show.
Walter Koenig is famous for telling fans that he was in the bathroom during that episode to explain his absence.