However, when any of my client/users send email on the same domain, the users not on my server but on the same domain, the Exchange server doesn't send mail. When a client/user sends mail to any other domain (e.g. hotmail, yahoo, etc.) the Exchange server does send the mail.
That's the scenario. Can you help me out?
Ideally, you should move the externally hosted users to your in-house Exchange server. You can provide them access remotely using Outlook Web Access (OWA), RPC over HTTP, or using IMAP4 and POP3 protocols.
If this is not feasible for any reason, you will need to work with your hosting company to implement the shared namespace. One way of doing this is to uncheck the "This Exchange Organization is responsible for all mail sent to this domain" checkbox in your Recipient Policy rule for that domain. Next, you need to create an SMTP Connector for your domain. Insert your domain name in the Address Space tab, and your hosted server's fqdn or IP address as a smarthost. This tells Exchange that your organization is sharing the namespace, and all recipients for your domain that cannot be resolved locally should be delivered to the externally hosted server.
Your ISP will also need to configure their mail server appropriately so mail for your Exchange users is delivered to your servers.
You can avoid this complication by simply hosting those users on your Exchange server, and pointing the MX record in the external DNS zone for your domain to your Exchange server.