Paladin accidentally connected to evil god and doesn't know it!

[Nibbens]

And how exactly do you plan to ALLOW them to 'earn' that knowledge? As I mentioned earlier, the GM is the players' eyes and ears (and Detect Evil) in the world, so if you lie to them, they literally have NO OTHER WAY of figuring things out.

I disagree. DMs lie all the time and PCs still come to discover and thrive in environments of partially correct information. If the DM knows his audience, and knows how to be fair and balanced with to his players expectations, then this can be a rewarding experience.

Besides. DMs are made to lie via the rules. Theres several skills devoted to it - bluff, intimidate, disguise. And an entire magic school based around it - illusion. Saying that a DM shouldn't lie because pcs have no other way to figure things out is a bit of a stretch.