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@example.com
Use STARTTLS – Checked
Server Requires Auth – Checked
Username – firstname.lastname@example.org
Password – admin accounts password
Use CRAM-MD5 – Unchecked
Trackback from your site.