The sorcerer-kings (some of them, at least) position themselves as gods to the ordinary people, and they even empower their templars with something that in every other context would be divine magic. So at least (byby-the-book), religion could be used to gain knowledge about sorcerer kings and their templars.
In addition, the halflings in the forest ridge remember the Green Age of Athas, and their beliefs (asas described in one of the Prism Pentad Novels) is are quasi-religious.
Finally, I think it's nothing out of the order for people to believe in deities, even if there is no proof of their existence. I'd guess most of the desert dwellers such as the Genasi, elf or half-giant tribes have their own beliefs.
So no, the Religion skill is not useless at all.