Make sure your Avaya phone system has been setup with a routeable DNS Server per http://pariswells.com/blog/random/avaya-ip-office-default-gateway

Create a user in 365 with a License 

On the IP Office under the SMTP Tab put the following:
Server Address – smtp.office365.com
Port – 587 – Mine was intermittently working with 25 so I switched it and it has worked on 587.
Email From Address – [email protected]
Use STARTTLS – Checked
Server Requires Auth – Checked
Username – [email protected]
Password – admin accounts password
Use CRAM-MD5 – Unchecked