Many people feel that Paladins are gimped. So I propose the following for them: Make them more fun by following the PnP rules more closely.
To that end, any Paladin that completes 'Running With The Devils' by associating with a party that is willing to kill Eladrin, should have his alignment changed to Lawful Neutral and lose all paladin abilities.