It's not a game mechanics issue. It's a player issue. Religion can be made important and influential if the players allow it to be that way. Adding mechanics that force religion on people will only piss off players and drive them away. If the players want it, it's there. If they don't, then they don't.
I honestly see religions being much more of a mechanics issue than alliances. Yet big restrictive ideas were being chanted for complicated treaties that wear down while basic extremely simplistic demands for religions were turned down. A paranoia about possibly having alliances creep up in too great a numbers is apparently more determining than an easy observation on how most stable religions have no content whatsoever. And don't go telling me that it's harder to write a short paragraph about whether you believe in an afterlife or not than finding someone to become an ambassador, sending him to another realm, having him negotiate an agreement, have the other realm do the same process, approving said treaties on both sides, proposing them, signing them, and then after all this, maintaining them...
