Helo command rejected: Host not found

Try the DNS Report test at www.dnsreport.com .  It may reveal that your domain has no RDNS or SPF, or something like that.  Normally, this wouldn't be a problem, but some domains are starting to insist on it.

I ran our domain (laborie.com) through dnsreports and I did see some warnings but I was not really sure on what if anything I needed to do.  One of the warnings was regarding the lack of an SPf record.  How do I create an SPF record? Is it through our ISP or is it a setting in exchange server?

or you may want to verify that the mailbox you are sending to is valid.  
beijinglaborie@sina.com did reply so the distant end is operating to a degree.

I wonder if the distant end is being used as a relay to lab-mail1.laborie.com and there are problems on the lab-mail1.laborie.com  end.

Regards,

There is also another warning from DNS reports regarding Mail server host name in greeting.  I would think that this is causing the problem since it specifically mentions HELO.  The warning references ntmain.laborie.com which was our old mail server, we recently switched (in Oct. 2005) to Exchange 2003 and our mail server is now lab-mail1.  Is it possible that I need to update the information somewhere to lab-mail1 intead of ntmain?

Whoever maintains your authoritative DNS record will need to add the SPF record .  There is a wizard to create the actual text at http://www.openspf.org .  Most people don't yet have SPF records, so only a really fanatical admin would block your email because of that - but it is still one possibility.

check out www.dnsstuff.com again, I don't see a MX or A record for lab-mail1.laborie.com.

I am a little unfamiliar on DNS and Mx records (and many other things) so forgive my ignorance here.   If you enter just laborie.com then their is an mxrecord but it comes back with ntmain.laborie.com (our old no longer running mail server), not lab-mail1.laborie.com (the new and much better mail server).  Does that mean that I need to contact the company that maintains our domain and update the mx record? Do I also need to have them create an mx record for lab-mail1.laborie.com?

It sounds like it. Either the SMTP relay knows specifically where to forward the email to (I assume that  beijinglaborie@sina.com is doing relay service) or it is using DNS to resolve lab-mail1.laborie.com via a MX or A record then send it.  If the latter is the case, talking to your ISP to change the record from ntmain.laborie.com to lab-mail1.laborie.com would be the best thing to do.

Regards,

It doesn't really matter what you internal DNS server names are, but it will help if you get the server to announce the same name as your MX records contain.  Look at the properties of your Default SMTP Virtual Server in ESM, and click the Delivery tab, then the Advanced button.  If the Fully-qualified Domain Name field is empty, then it may help to put the name from your MXrecord in there, so that the rest of the world knows that it's the same server.

The fully-qualified domain name field was not empty, it had lab-mail1.laborie.com in it so it looks lik updating the record from ntmain.laborie.com to lab-mail1.laborie.com wouldb be the way to go.  Thanks.

It's worth a try.  Your MX records simply supply a name that gets mapped to your IP address.  This input field tells your server how to introduce itself.

I am still interested in finding a solution.  On DNS reports, I receive the following warning.  I am not sure if this is related to the problem or not.  The warning is "Mail server host name in greeting" and the description of the warning is "One or more of your mailservers is claiming to be a host other than what it really is (the SMTP greeting should be a 3-digit code, followed by a space or a dash, then the host name). If your mailserver sends out E-mail using this domain in its EHLO or HELO, your E-mail might get blocked by anti-spam software. This is also a technical violation of RFC821 4.3 (and RFC2821 4.3.1). Note that the hostname given in the SMTP greeting should have an A record pointing back to the same server. Note that this one test may use a cached DNS record.

lab-mail1.laborie.com claims to be invalid hostname 'SMTP':
   220 SMTP service ready

We do have a firewall.  I got some help setting it up so it is possible that it was setup this way.  Glad to hear that it is a common setup.  Thanks.