voicemail to email for external calls is not working for some calls

[Isaac]

whenever someone externally calls in and leaves a voicemail users won't be notified half the time and the other time they will. Internally this all works as it should, it is only when someone calls in externally.

[Vaijanath Sonvane]

Are the incoming calls coming on same or different PRI/SIP Trunk lines? If it is different, then do you have correct Calling Search Space (CSS) configured on it with access to voicemail partition.