Quand vous touchez un ennemi avec une attaque d'opportunité, vous pouvez vous déplacer de la moitié de votre vitesse tout de suite après l’attaque, lors de la même réaction.
La règle me semble claire: le déplacement du paladin se résout pendant la réaction de l'AO, tout de suite après l'attaque du paladin, donc avant que l'ennemi ne continue son déplacement.
En ce qui concerne d'expliquer ça en jeu, il y a plein de façons de le faire. C'est aux MJ et joueurs de trouver une explication narrative qui les satisfasse. Par exemple:
Simultanéité: D&D représente les actions en ordre séquentiel durant un combat, mais souvent pour l'aspect narratif on considérera que certaines ont eu lieu en même temps. Autrement dit, la résolution mécanique est séquentielle, mais on raconte les actions comme si elles avaient eu lieu en simultané.
Séquence: le paladin cible la jambe de l'ennemi avec son coup, de manière à retarder quelque peu le déplacement de l'ennemi, juste assez pour lui permettre de faire quelques pas rapides, avant que l'ennemi ne continue.
Il y a par ailleurs des situations avec des réactions en chaîne qui pourraient être interprétées comment prenant encore plus de temps que les quelques pas du paladin dans une telle circonstance, et qui interrompraient le flot normal du combat d'une manière qui semblerait bien plus significative que le déplacement permis par Vengeur Implacable. Par exemple, plusieurs PJ pourraient préparer une action ayant comme déclencheur l'arrivée de l'ennemi à une même position donnée, ou ayant des déclencheurs interdépendants. Il faudrait alors résoudre de multiples actions au milieu du mouvement de l'ennemi. Parmi ces actions, peut-être qu'un des PJ lui-même aurait préparé l'action de course, pour se déplacer vers la position de l'ennemi. Et cela provoquerait peut-être un AO de la part d'un autre ennemi. Etc...
Bref, Vengeur Implacable ne me semble ni confus, ni impliquant une mécanique inhabituelle. Une réaction est simplement comme une parenthèse: on l'ouvre après que le déclencheur ait eu lieu, on résout ce qu'il y a à résoudre, ensuite on ferme la parenthèse et on continue le flot normal. S'il y a un nouveau déclencheur dans la parenthèse, alors on en ouvre autre, qu'on résout, avant de fermer la seconde parenthèse; puis de finir de résoudre la première; pour enfin reprendre le flot normal du jeu.
Ici, il y a une seule parenthèses, mais deux éléments à résoudre dans celle-ci (AO + déplacement du paladin), avant que le flot normal du jeu ne continue: l'ennemi termine son mouvement.