SMTP issues (SBS 2003)

This is a sporadic problem that I am trying to resolve. Users receive bounce back error messages such as the following.
There was a SMTP communication problem with the recipient’s email server. Please contact your system administrator.

There is no open relay or blacklist, and this is a new Server. Sometimes the users will get relaying is denied or you don’t have permission to send.

Thanks for any help you may provide.