Sejs
First Post
Arnwyn: I think you might be wrong here - IIRC, PHB paladins don't even need a god.
Paladin class, religeon section: "A paladin need not devote herself to a single diety - devotion to righteousness is enough."
Similar in concept to how you can have a cleric of No God In Particular. You don't have to be a devotee of Shabadoo the God of Healing - if you've got the devotion to go out and do the right thing, then the powers that be just see to it that you get your domains, spells and so forth. No purchase necessary.