1. The entire book Splinter of the Mind's Eye is between the movies. It features the "first" Vader/Luke direct confrontation.
2. Luke helps in the evacuation of Yavin 4, slipping in and out past a Vader-commanded blockade.
3. Luke, with information from Imperial Admiral Griff (don't recall if he was being traitorous or trying to trap Luke), attempts to sabotage and destroy the Executor as its being built at the Fondor shipyards, again, under Vader's nose.
During all that time, Vader would have had to learn who this Alliance operative is.
BTW: MagnoliaFan, while its not exactly canon and (now) contradicts EP2, the Emperor was definitely not pleased.
In one of the Zahn books (think its the last one The Last Command, Mara Jade tells Luke (and us) about how displeased the Emperor was. I don't recall the exact line, but she says something to the effect of "Why do you think he had a mechanical left hand?"
Meaning Vader lost it to the Emperor as punishment.