Well, a Paladin or Cleric must have a belief system of some sort in order to derive spells by way of meditation. Both are certainly concerned with spirituality. It wouldn't actually be much of a big deal for Wizards to research Cleric Spells, the other way round would be the problem!
I would agree that most played Paladins do tend to support a religion. The PHB, though, says that "Paladins need not devote themselves to a single deity. Devotion to righteousness is enough for most", so I would have to conclude that in core D&D, most Paladins do not support any one Deity (The huge exception to this is the Forgotten Realms).
The point, though, is that serving one God does not mean ordained. A Paladin may become ordained, but that is not the same thing as supporting or being supported by a particular divinity. So, Paladins are, by and large, secular figures.
Whilst unordained Clerics does sound odd, it actually is not too silly, being as it allows for the non-secular unordained (i.e. men who would have been ordained, but who for whatever reason have not been, typically loners, savages or frontier men).
Technically correct is the "best kind of correct" to paraphrase a certain fictional character.
To be clear, though, I am not opposed at all to Paladins serving a Deity or being ordained. I just thought I had better point out that they don't have to be and the PHB implies that most are not.