Add an MX record
If I'm understanding you properly you're running a Windows 2003 AD domain but are using your ISP for all mail handling. And that you Windows domain name is the same as the ISP mail? If this is the case I'd say your most immediate problem is that your clients are resolving DNS against your WIndows domain and there is no MX record. You should add an MX record in your DNS server that points to your ISP's mail server.
If this isn't the case another thing you might want to look at is SMTP authentication. There is a setting in Outlook that says something to the affect that mail server requires authentication. I can't verify the syntax because I don't have Outlook installed ion this PC but you might look for this setting and give it a try.
