My biggest problem with this entire scenario is that it's been engineered to screw the paladin, as others have said. It's not a moral dilemma, it's a moral trap.
Examples of moral dilemmas:
1. The One vs. the Many: An evil god's holiest day draws near. The paladin learns through dreams that two priests of the evil god will be performing fell rites in his name. Only the paladin can stop them, yet the priests are located hundreds of miles apart, and he can only stop one of them. Does he ride to prevent the pure maiden from being sacrificed, or does he leave the maiden to her fate and ride to prevent the other cleric from poisoning the town well? Here, the dilemma ties into the philosophical question of the one vs. the many. Some philosophers believe many lives are worth more than one, others believe that you cannot quantify quality of life, and the maiden should have the same right to be saved as the villagers. The paladin must decide. Either way he is performing a good act, but in either case, he must live with the knowledge that he could have prevented the other death(s) if he'd chosen.
2. Evil Now vs. Evil Then: A tyrranical overlord puts a young knight's family to death. Years later, the overlord has a change of heart and gives up his power, retiring to a small village to tend to the land and repent. However, the knight cannot forget the death of his family. He pursues the overlord, performing several morally questionable acts in the process. While the paladin is visiting the village, the knight finally catches up with the overlord. This scenario revolves around past and present evil, and what justifies killing. The knight was good, but has fallen into neutrality, the overlord was evil but has risen into neutrality, now they come into mortal conflict right before the paladin's eyes. Does he side with the knight whose family was killed? Does he side with the overlord trying to become a better person? Does he allow them to cross swords and let fate decide? Here, the paladin can take any number of actions, but inevitably he'll be forced to truly examine the morality of the situation, and make some hard judgements.
These are the kinds of situations that I think paladins should be faced with. Situations that cause the player to look at morality, to make decisions that they may not entirely be comforable with, to examine what justice and honor really mean.
But I don't think that by deciding on a paladin, the player implicitly or explicitly agrees into being railroaded into losing his powers. That's just bunk.