But @Niara, you are leaving out the part about what happens to the souls of the faithless in the D&D Multiverse. Not a good idea to be faithless.

And also, to again reiterate, the point is NOT that a paladin MUST have a patron deity. The point is that in the Forgotten Realms setting, paladins having patron deities is what is the norm, even though not having a patron deity is allowed.