We recently setup our Office365 solution.  I have clients able to connect and the Microsoft Remote Connectivity Analyzer gives me a green light for all of our email boxes.  When I try and send a test message from another domain (i.e. gmail), I receive the following error:

Delivery to the following recipient failed permanently:

**********@netvious.com

Technical details of permanent failure:

Google tried to deliver your message, but it was rejected by the recipient domain. We recommend contacting the other email provider for further information about the cause of this error. The error that the other server returned was: 550 550-Please turn on SMTP Authentication in your mail client, or login to the 550-IMAP/POP3 server before sending your message. mail-yw0-f52.google.com

550-[209.85.213.52]:58147 is not permitted to relay through this server without 550 authentication. (state 13).

I get the exact same result from another domain that is running Exchange 2010.  When I send an email message to any of our addresses, it gets bounced.  The Microsoft Remote Connectivity Analyzer works perfectly though.

Any thoughts?

Thanks!