Okay time to get controversial <g>
I tried to express this once on SKR's boards but the young'uns brandishing thier PHB's as some holy item were having none of it
My own take on Paladins is this.... as they are presented in the PHB they suck eggs big time... they are a stereotype. Lawful Good Cavalier'esque run around do good deeds always stuck in the one mould no matter how much you want to vary them.... phhht.
Paladins "Should" IMO be a split into three types Good/Neutral/Evil each with variant abilities and more options included to vary them even more, then and ONLY then you may be able to get Paladins (and no I don't mean holy warriors) for all religions.
I'll explain, to me a Paladin is feasible for ANY religion if they can exist for one, they should exist for all, but you cannot have one "do gooder" class that will fit all.
If a warrior grows up in a region that is predominently evil and is taken into the church and trained to be a paladin of that evil good...somehow I just don;t see him curing disease, protecting from evil, saving maidens and obeying the law... no no, instead he will uphold those beliefs of his church and retains at the heart of it cultural teachings common of his home regions which as I mentioned in this example is predominently evil. Some might say well sure but that aint a paladin... well yes IT IS, it just simply isn;t possible as the PHB version stands.
If you also consider an Elven Paladin brought up in an elven society (and thus holding elven cultural and societal beliefs) taken into an Elven Church of a good who say is all about protecting elves from decline, and promoting elven interests. well firstly as a people Elves are predominently Chaotic Good.. so if they did have Paladins would they be Lawful Good... not a chance! would thye obey the code of chivalry as a human LG Paladin stereotype would?......no of course not they would represent Chaotic good beliefs of his god and be working to promote all things elven as laid down in the tenets of his relgions...... again some might say this is not a Paladin....but YES it is.
This doesn't make a Paladin a Holy Warrior... a Paladin is a predominently martial promoter and crusader of a Religion.. but there are in most games far far far more religions than just LG.. some might say other paladins weren't included because they just don;t fit other religions..... but yes they really do AS much as they do an LG one.
Some even say "well just pick up a Prestige Class, blackguard for example"... but I say why should I need to pickup a PRC? the option to play an appropriate type of Paladin should be there from the get go, without having to resort to another class for it..
anyway there are my views on Paladins for good or ill, as presented they do nothing for me, they lack IMO the versatility they should have as a class. I can see heaps of potential in them, but instead of exploring that option they were instead shoe horned into one fit stereotypical mould.