MS Exchange server

We have installed Exchange server 2003 in our premises. We use (thirdparty.com) for managing external mail. We have two categories of user ? those having privilege to send mail locally only and second group having account ( name@mydomainname.com) created on thirdparty.com . There is some problem some where, we receive complaint from second category of users that sometimes they do not receive external mail etc. Problem is not consistent.