I receive the error "we do not relay"

There are two common causes.

You may be using more than one mail account from more than one provider in the client, and you are attempting to send mail from one domain, through the other domain's email server.  That second server will reject the mail since it's not local.  A bit like trying to send a NZ post package with DHL.

For example, if you try to send a message with a source address of shayne@yahoo.com though our mail server, we will reject it since we don't look after yahoo's mail.

This error can also occur if you haven't set up SMTP to use authentication correctly.  Our mail-server will only accept mail from authenticated users.  However if you've just logged in via pop3 or IMAP, the server remembers this (a feature called "POP before SMTP").

If you check you mail, read something, and then send a reply a while later, your pop before SMTP timeout may have expired, and then when you click reply it fails.  Then you check your mail, and then send again and it works.  Magic.
Set up your mail client to log in with SMTP though, and that goes away.

Take a look at our recommendations for setting up the email client on our help-desk site, and make sure you're set up like that.  That should clear up this error.

Our support home page:
http://support.enlightenhosting.com

The mail settings you should use:
https://enlightenhosting.zendesk.com/hc/en-us/articles/205553113-Basic-e-mail-client-settings

A walk-though for setting up Outlook 2013:
https://enlightenhosting.zendesk.com/hc/en-us/articles/201260855-Set-up-Email-with-Outlook-2013-on-Windows