jchristman2002,
The Welcome Message from the Mitel 5000/MiVoice Office 250 is sent via SMTP and not the route that email may take through IMAP; that may be causing some of your confusion.
So with what you are saying you have your E-Mail Gateway setup just fine under System\E-Mail Gateway as well as System\IP Settings for the DNS Suffix as well as DNS servers.
What you may not have setup correctly is the remainder of what is needed for Enhanced Integration to work so start looking at that.
Thanks,
TE