Yet we just went through the multiple justifications and reasoning behind people joining and following an evil deity. If an evil church or religious group poses no immediate or obvious danger to the region or its government, and, as mentioned, actively aids and helps the region, why would people be opposed to having them around?
Deities like Talona are obvious exceptions, although I could see certain governments allowing even them to function in the area if guarantees were met and honored. However, in general, why would deities like Beshaba, Umberlee, Cyric, or Shar be eliminated from the larger cities and civilizations of the Realms?
Having Clerics of power around would further stabilize just about any region, as well as provide invaluable services to the established government and the local populace. The reason I must ponder this is, as I said, I have to consider how religious faiths would integrate themselves into society, and by offering their services and loyalty to the region, they could secure a solid, stable, secure base to which to spread their faith.
So, logically, they would take this action. The question then becomes, if said religions are willing to do so, what would be stopping them? Really, I can't see why people or leaders would flat out refuse this offer and opportunity unless they were already beholden to other faiths that diametrically oppose those seeking entry.
On another note, I would concur with what Kae'Yoss said. If you think about it, this resolves a number of the issues one may have with the power scheme listed in the FR books. It mentions in the Cyric entry in the FR campaign setting book, that his followers involve themselves in intrigues that lead to strife and murder, rather than war, as if they did the latter, the world would fall under the sway of Tempus.
This indicates that actions and events taken by people or organizations in the world directly influence the power and strength of the deities who have dominion over those areas of life. This would mean that, for example, every time someone tells a lie, Cyrics power is increased, or every time someone hides a secret, Shars influence is increased, and so on, and so forth with all the varying deities and their realms of dominion.
That would explain why dieties like Shar and Cyric who may not have as abundant a following as say, Lathander or Chauntea, still have extremely high levels of power and influence in the world, as people consistently and routinely engage in activities that further their power across the Realms, without ever actually directly worshipping them.