Yes I can defiantly ping the exchange server from the linux box.

you didnt give response to the other command (telnet)?

Sorry, I can also telnet onto the email server.

from any windows command prompt do:
# ping -a ip.address.of.exchange.server
and check the response (what the ip resolves to) You might be having a serious flaw in the whole architecture (mail sub system + dns) Do you have your own dns server?

The ping test didn't resolve to a hostname it just pinged the ip address of the mail server. We host DNS internally.

I know why that didn't work, it's because there is not a PTR record on the reverse DNS lookup zone. Though it still doesn't explain why I am having problems with FQDN of the server when that is added to the smart host option. As I can resolve that to an ip address fine.

When I add the -a switch to the ping command it now resolves the ip address to the FQDN of the mail server, from a windows command prompt.

Got it to work.

I did a re-install of Ubuntu and then installed OpenEMM and Sendmail. This time I only added the define(`SMART_HOST', 'example.example.local')dnl to my sendmail.mc file and it worked almost straight away.

I will post my installation notes up when I have more time.

Obviously when you put in ip.ad.dr.ess you mean something like this: 192.168.1.100, or whatever the local IP address of the exchange server is.

Yes that is correct.