I have an Exchange 2003 SP2 serving about 100 mailboxes. Recently someone from a different company tries to email to someone in the organization. The message disappears and the sender doesn't get an error message. It is not blocked by SPAM either. The sender has been added to the Safe Senders list in ESM. Checking the logs I can see that the message makes it to my Exchange but it is nowhere to be found.
Strangely, if this sender replies to an email sent from someone in my Exchange it makes it just fine without any issues. Same thing if he tries to forward someone else's message. The issue occurs only with new messages.