mail not working with company id

Hi,

I have a fresh new installation of red hat linux. I am trying to send an email from the "mail" utility from inside my Linux box to my company id "xxx@company.com". We are using microsoft exchange server online version to host our company's email.

I am able to send emails to gmail and yahoo but not to my company id. What do you think could be going wrong? Is it something like I dont have SMTP host defined for my company id?

Thanks for your help..
Pri.

---------- Post updated at 04:31 PM ---------- Previous update was at 01:24 PM ----------

Update: so I just ran exim in debugging mode and attached below are the results of that.....our email is hosted on "Smtp.mail.microsoftonline.com"

Where do I need to specify that the rmail or mail utility or even exim has to use that when sending mails outside of the local machine.

-------------------------------------------------------------------------------------------

Exim version 4.63 uid=0 gid=0 pid=28776 D=fbb95cfd
Berkeley DB: Sleepycat Software: Berkeley DB 4.3.29: (July 12, 2010)
Support for: crypteq iconv() IPv6 PAM Perl TCPwrappers OpenSSL Content_Scanning Old_Demime
Lookups: lsearch wildlsearch nwildlsearch iplsearch cdb dbm dbmnz dnsdb dsearch ldap ldapdn ldapm mysql nis nis0 nisplus passwd pgsql sqlite
Authenticators: cram_md5 cyrus_sasl plaintext spa
Routers: accept dnslookup ipliteral manualroute queryprogram redirect
Transports: appendfile/maildir/mailstore/mbx autoreply lmtp pipe smtp
Fixed never_users: 0
Size of off_t: 8
changed uid/gid: forcing real = effective
  uid=0 gid=0 pid=28776
  auxiliary group list: <none>
seeking password data for user "root": cache not available
getpwnam() succeeded uid=0 gid=0
configuration file is /etc/exim/exim.conf
log selectors = 00000ffc 00089001
trusted user
admin user
originator: uid=0 gid=0 login=root name=root
sender address = root@lillypoo.company.local
Address testing: uid=0 gid=93 euid=0 egid=93
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Testing priya@company.com
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Considering priya@company.com
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
routing priya@company.com
--------> dnslookup router <--------
local_part=priya domain=company.com
checking domains
company.com in "@ : localhost : localhost.localdomain"? no (end of list)
company.com in "! +local_domains"? yes (end of list)
calling dnslookup router
dnslookup router called for priya@company.com
  domain = company.com
DNS lookup of company.com (MX) succeeded
DNS lookup of www.company.com (MX) gave NO_DATA
returning DNS_NODATA
DNS lookup of company.com (AAAA) succeeded
DNS lookup of www.company.com (AAAA) gave NO_DATA
returning DNS_NODATA
DNS lookup of company.com (A) succeeded
192.168.2.107 in "0.0.0.0 : 127.0.0.0/8"? no (end of list)
fully qualified name = company.com
www.company.com 192.168.2.107 mx=-1 sort=-140 
set transport remote_smtp
queued for remote_smtp transport: local_part = priya
domain = company.com
  errors_to=NULL
  domain_data=NULL localpart_data=NULL
routed by dnslookup router
  envelope to: priya@company.com
  transport: remote_smtp
  host www.company.com [192.168.2.107]
priya@company.com
  router = dnslookup, transport = remote_smtp
  host www.company.com [192.168.2.107] 
search_tidyup called
>>>>>>>>>>>>>>>> Exim pid=28776 terminating with rc=0 >>>>>>>>>>>>>>>>

check with the company exchange server if the port is open for mail

Company exchange server is hosted on microsoft exchange online services....so its like sending a mail from unix to yahoo (as the email is not hosted inside the company)