unauthorized relay traffic prohibited

[NTSGuru]

I'm a new Exchange Admin (well, trying to be) and I can't figure this problem out, so I hope some of you gurus out there can help.

I have E2K set up on my W2K Advanced Server (fresh installs for all of them) with Active Directory. I am able to send/recieve mail for the most part. All mail out of the building gets to it's destination. However sometimes mail is not able to come back into the building from outside email addresses. When an inbound email fails, the sender gets this error :

----- The following addresses had permanent fatal errors -----
<fred@myServ.com>

----- Transcript of session follows -----
553 <fred@myServ.com>... unauthorized relay traffic prohibited
554 <fred@myServ.com>... Service unavailable

This does not ALWAYS happen!!! That's the part that I can't figure out. I've had someone send an email and it works fine. 10 mins later the same person sends another email and gets that error! If they wait for a while then they can send again.

It's like the Exchange version of Russian Roulette! For the life of me I can't figure out what is causing this error!!

Any and all help is greatly appreciated. This has been happening for a couple months now, and I'm at my wit's end.

TIA

Fred