Glad to see i'm not the only one using exchange 2003 on here. First thing you need to do (which has already been said) is have your mail server ip address added as an A record. For instance use M1.****. Then have them set your MX record to point to M1.****. The reason for this extra step is so that a recursive check of the servers name will show that it is indeed comming from the correct domain as well for outlook web access.
The second change needed is only if your email is blocked due to your ipblock. For instance when a remote mail server checks my mail servers ip address it is returned as XXXX.il.comcast.net. Most mail servers who use horrible blacklisting software will not accept email which comes from home internet connections. To resolve this follow this link http://support.microsoft.com/kb/821911 which should take care of any problems you have.
Hope this helps more than confuse. sometimes i don't explain things very well.
--I just tried this myself and discovered one fatal flaw... They only gave you half the info you need to finish this. you will also need to add the smarthost info to your internet mail connector as well as set it up for authentication. If your going to try this, reply to this post as i'm still trying to get it to work with dns still propogating for my domain
