Well, to clear up some things from the post:
Shar is the Mistress of the Night, the Lady of Loss. Her portfolio includes caverns, dark, dungeons, forgetfulness, loss, night, secrets, and the Underdark. Her followers include assassins, shadowdancers, etc... but they also include those who have lost someone or something they loved. Her worshippers include people who believe it's better to cease to exist than to live with the pain.
I agree. Any priest or follower of a religion should be able to find out if there is a group of likeminded individuals in a city. It's nothing stranger than the old fashioned way bums in the US would 'mark' towns at the outskirts, so fellow hobos would know 'this town is cruel to bums' or 'there are always free handouts'.
I don't see someone following an evil goddess in FR having a problem. Forgotten Realms is different in that the gods do not penalize you for making 'bribes' to other gods; that is NOT worship. A good example are the sailors who make donations to Umberlee, so that she doesn't sink their ships.
Rambling, but ... in short: Shar is not an overtly destructive goddess; she's into entropy and everything in the world devolving; her followers include those who have nothing left to live for, those who drown their sorrows or try to chase away the memories with drugs, and hedonism. And, major gods should have some sort of center of worship - be it secret or not - in larger communities, probaby openly in major cities.
Besides, churches in game do a lot to help move the plot along. "Sure, we can heal you, but... we need this favor from you in exchange..."