Ah, see I don't see religion as being the most important attribute of a Paladin. For me, being a Paladin is about playing the idealized knight - a paragon of chivalry and courtly love, etc. To me, a Paladin is defined as a Knight of the Round Table or one of the Twelve Peers.
I don't disagree with your earlier statement that Lancelot or Galahad could also be considered Paladins (and perhaps better examples than Gawain overall). It is just that my basis for the ideal Paladin is Gawain in Sir Gawain and the Green Knight. Within the confines of that story, and a few others, Gawain exemplifies the characteristics that define a Paladin. He shows himself to be honorable, courteous, and demonstrates the codes of chivalry and courtly love. Those are the characteristics I use when define a D&D Paladin. Religion is important, but not as important as those other virtues.