In general, the paladin did right. He stopped the man in the middle of perpetrating evil.
As far as his methods, the paladin shouldn't be given any more punishment than having to say a few prayers of penance for rash action and not putting the fear of divine retribution into the molester. And even if that means kneeling for a couple of hours in front of the alter saying the prayers or wearing a hair shirt for a day, the paladin should be happy to do it. No loss of paladin powers.
I'm constantly amazed at how often people are so strict about paladin powers even when it's clear that the paladin stopped evil from being committed (in this case, committed again). The paladin should be lawful and yes, that does mean having respect for the legal system and legal authority as well as having discipline, but let's not be ridiculous. Not every infraction has to be met with stripping of powers. Minor offenses should be met with relatively minor atonements like extra work at the temple, extra prayers, extra tithing, or minor corporal punishment.
Actually, I'm reminded of a book called Biting at the Grave by many of these sorts of debates. In it, the author, Padraig O'Malley, talked about the trouble in Northern Ireland within the context of the H-Block hunger strikes. While often called a specifically political conflict rather than religious, he takes it right back to religious. Because of their respective educations, mostly parochial, the two communities can't communicate on moral issues. For the Protestants, it's all black and white, sin or no sin. For Cathoics, it's shades of gray, venal sin and mortal sin. Protestants think that Catholics are too morally ambiguous and Catholics think Protestants are too rigid. And so they can't communicate on moral issues.
What I'm seeing here, and in most paladin debates, is too much Protestantism, binary sin vs no sin, too much absolute rigidity. What you need is more gradations of violations for a paladin and appropriate penance for those gradations. It fits a more medieval-based fantasy religion anyway. Make the paladin take a half day out for penance and leave it at that. Don't strip his powers for doing his job, make him work off using non-paladinesque methods.