Email rejected from certain hosts

I run an Exchange 2003 server that receives & routes email
directly to the internet via SMTP. (It has a valid MX record in the
zone held at my ISP.) This server also is the primary DNS for my
local network.

I have followed the MS-recommeded .local for the local network,
with a .com domain on the same server connected to the
internet.

PROBLEM: 99.9% of my email goes with no problem. But, I have
some users that have problems sending to a couple of different
domains. In all cases, I get a failure report from the receiving
server denying the message, saying that “relaying is not
allowed”. I have checked my servers configuration and cannot
see why it would appear that I am forwarding…..

What else can be causing this problem?