I'm not sure if this is the right area to ask, but here we go. I have a client who has a couple websites on a Windows server with MailEnable as the mail manager. Any emails being sent from the server work great, except when sending to some domains, the message does not go through due to the following error:

12/13/11 01:15:56   ME-I0026: [86476200E5834227A819E6E63E0EFDA2.MAI] Sending message 
12/13/11 01:15:57   ME-IXXXX: [86476200E5834227A819E6E63E0EFDA2.MAI] Remote server returned a response indicating a permanent error. Server Response: (550 Relaying not allowed**)
12/13/11 01:15:57   ME-E0036: [86476200E5834227A819E6E63E0EFDA2.MAI] MAIL FROM command Failed.

Can anyone give me some leads on how to correct the settings to allow emails to go through properly? In particular, the emails are not going through to a Network Solutions email account and Network Solutions has not been very helpful thus far.

In addition, can a domain's DNS settings affect this error? Currently, the domains are hosted by Network Solutions and use the Network Solutions email service to send/receive email. The server is located with a different company and the Domains' DNS points to it. Which mail related DNS entries are allowed or not allowed in this scenario? Thanks