Are they getting any error message?
If you are in control of the SMTP mail server, then you need to look at
the mechanism that it is using to identify authorized users. It appears
that it is not recognizing your users as authorized.
Many SMTP mail servers require that you be directly connected to their
service (not via another ISP, another corporate LAN, etc.) in order to
send via their SMTP mail server. (They match your IP address against
those owned by the service.) An exception is made for messages being
sent to recipients of their service. The typical error message will be
"Cannot Relay" or "Not Local" or "Not Gateway", "Not Allowed Rcpthost"
or something similar.

Signature
Mike - http://pages.prodigy.net/michael_santovec/techhelp.htm
> My users are experiencing some trouble sending/receiving emails
> through
[quoted text clipped - 8 lines]
>
> Thanks