Priest can talk to anyone of their faith, and likewise have all the other option for talking to nobles outside their realm, IE if they travel to another realm they can talk to nobles in whatever region they are in. The fact that most realms only allow one religion is not due to something religion lack, but the fact that too many realms want to ensure they can't fall prey to something like a RTO, so they create a religion to defend their realm against other religions.
Other then that, it takes ALOT of work to establish a religion in even 1 realm. It takes a whole heap of work and several more dedicated nobles to spread it further.
