host unreachable

We are using MS exchange server V5.0 for our e-mail and we find it very unreliable. Sometimes we can send e-mail outside our company but there are times that we can’t send. We have this error “host unreachable” specially we this email format.(test@mac-shangri-la.com)but when I send to a hotmail account it is successful.And also everytime I restart my server I need to stop & start the “internet mail connector” for us to send email outside. What could be the problem. Please I need some help. Thanks.