Mail Server/Exchange Send bounce

I'm running a CentOS 4.2 email server and an Exchange 2003 box, but I'm having problems with one (or both). I didn't build the system, and my boss won't let me touch them in terms of upgrading or starting over (which I have been begging for since May). Anyway, I don't bother with the exchange server and go straight to the CentOS box for my email and have no problem with it. There are some users on the network that connect through the exchange box and they are having email issues. Many can get emails in from the accounts that we host on the CentOS box which are not part of the Exchange, but if they try to reply to those emails, they get an immediate "Undeliverable" failure. These same users have no trouble sending to anyone else, it's just emails that we host. Any ideas?

Another issue is very poor delivery times from incoming emails from other networks, sometimes upwards of 2 days, but not consistently. I don't know if these issues are related or not.

Is there anything else that goes along with the message; other than undeliverable (anything in the logs as well)? Undeliverable sounds like it may be a DNS issue (or some other similar error where it can't resolve an MX record for that domain).