So they have set up a SMTP relay internally for you to send mail to? Have they allowed the IP address of the mitel to relay mail through it? Also are other devices able to relay mail through it without issues?
It could be that they have not created a SPF record to allow for the relaying to work, or that the domain that the emails are sending from is not valid, so it is being rejected.
There are a few things it could be.