The problem I got started as an occasionnal problem. Some companies or clients could not send us emails, as they got the error 5.1.1 The recipient does not exist on the specified server.
This became more of a problem this week as nearly 25-35% of the incoming emails does not go through and return to the sender with this notice.
We did some testing and found out that when users send us emails this does not work, but I can send them emails. If they hit reply on my email it will go through properly and work with no problems most of the times.
I am on Exchange 2003 with Windows 2003 server on an IBM Netfinity 5500 server.