Login to the Plesk Admin Control Panel, Server --> Mail --> Relaying --> Authentication is Required, POP3 lock after xxx minutes, Smtp. Check both boxes. I use a default of 1 minute, as that limits my known users to only send mail one minute after authenticating with their account. (I use 5 minutes).

This allows my users to send e-mail from their pop/smtp account to users outside of the domains I host (i.e. "myisp.com"). This should correct the problem you're currently having. However, you will need to make sure your users are Authenticating via the Pop server before attempting to send e-mail.

OutLook/OutLook Express -> Accounts -> Account Name -> Advanced Options/More Options -> Smtp -> Check the box that says "Requires authentication prior to sending" and tell it to use the "Pop Server" for authentication.