The religion skill in dark sunDark Sun is not useless if you look at it from a different angle.
History is a more generalized skill so it is less likely that you would have a character that studied history know about the old religious objects that are still around even though the gods are not.
Ex. the party is in a dungeon that a use to be a temple to [insert god here] and have come to a door that is only activated by answering specific questions about the deity or how that religion viewed history, this would make the history check for the challenge much harder then a religion check.
There
There are other ways to use the religion skill as a main skill in challenges or for interpreting religious texts on the walls of old tombs and such to help get to or around things. Remember that jestjust because the gods are gone now dosedoes not mean they were never there. Religious cults and peoples are known for theretheir odd ways, intricate religious objects, and mysterious places.
That is jestjust my take on the matter bass line is that you are the DM do what you fellfeel is best for your campaign and group, a finale. A final thought if one of your players has taken the religion skill try to let him use it every so often to make him or her fellfeel like they didn't waste a skill slot.