I dislike all examples involving omniscient beings.

I would also prefer to assume that natural selection endowed us with sub-conscious body language and other cues which make us very bad at lying.

The only thing Omega uses its omniscience for is to detect if you're lying, so if humans are bad at convincing lying you don't need omniscience.

Also, "prefer to assume" indicates extreme irrationallity, you can't be rational if you are choosing what to believe based on anything other than the evidence, see Robin Hanson's post You Are Never Entitled to Your Opinion. Of course you probably didn't mean that, you probably just meant:

Natural selection endowed us with sub-conscious body language and other cues which make us very bad at lying.

Say what you mean, otherwise you end up with Belief in Belief.