I am more than slightly befuddled then... Do you have entry in your DNS for the internal server name (ie. mail.domain.local) that you could change your mail settings to use that DNS instead of the .com address?
Also, as much as it pains to me to say this and I have scolded people for it on numerous occasions, you could try changing the field for SMTP E-Mail Server to the (GULP) server's internal IP address instead of the domain name... It is very bad practice but it could possibly verify that the Mitel and email server are at least talking to each other.
On another note, is NTP Time Synchronization working to an outside time server? (This would verify DNS connectivity for another site)