If you have problem sending email through Office 365 from Exchange 2013 try with this:
Set up your email server to relay mail to the Internet via Office 365
Next, you must prepare your email server to send mail to Office 365. This enables mail flow from your email servers to the Internet via Office 365.
On your SMTP email server, configure a Send connector to send email via a smart host to Office 365. For instructions on how to do this with Exchange Server 2013, see Create a Send connector to route outbound email through a smart host. For instructions on how to do this with Exchange Server 2010, see Create an SMTP Send Connector.
Here is an example PowerShell cmdlet to help you configure the Send connector in Exchange Server 2013:
New-SendConnector -Name "My company to Office 365" -AddressSpaces * -CloudServicesMailEnabled $true -Fqdn "cert domain name, such as mail.contoso.com" -RequireTLS $true -SmartHosts yourdomain-com.mail.protection.outlook.com -TlsAuthLevel CertificateValidation
https://technet.microsoft.com/en-us/library/dn751020(v=exchg.150).aspx?f=255&mspperror=-2147217396
