Persistent outlook cache issues in Exchange 2013 - what could be causing these issues?

Question

Mail server

I somehow solved the problem from the previous question with the queue. There was a problem with the cache.
The situation reaches the point of absurdity: a person sends a letter to the address "Vasya [email protected]", he receives an NDR address that does not exist, I connect to the person and delete this address from the cache, send the letter again - everything is fine, everything comes.
10 minutes pass, the person again tries to send to the address "Vasya [email protected]" and NDR comes to him again. Again we clear the cache, again temporarily everything is fine. What could it be? Many users have a problem with different versions of outlook - 2010, 2007, 2013. Everything is fine in OWA. The problem appeared after an unsuccessful server update, before that everything was fine.

Answer 1

The NDR text would greatly facilitate the diagnosis.

Answer 2

Very often this happens because of the Cyrillic alphabet in the email address.