I have one address on our exchange server that you suddenly can't email sent from outside addresses. You can send email successfully from within the same domain. The message gets to the exchange server but the log for the messages sent to this address is:
SMTP: Message Submitted to Advanced Queuing
SMTP: Started Message Submission to Advanced Queue
SMTP: Message Submitted to Categorizer
SMTP: Message Categorized and Queued for Routing
SMTP: Non-Delivered Report (NDR) Generated
This is the same for all messages sent to this address. I have a more than 300 mailboxes on the server and none of the others are having an issue. No firewall, routing, or DNS changes have been made recently. We use Trendmicro for our SPAM filter and then they pass the emails onto our exchange server. In their logs I can see where the messages clear their queue and are delivered to the Exchange server for delivery.
The senders never get and NDR sent back to them to see what the error might be.