Try updating the Recipient Update Service.
Open ESM, Expand the Recipients container. Click on Recipient Update Service.
In the right-hand pane right-click your Recipient Update Service and select “update now”.
If that fails to work, choose an off-hours time-frame and choose the “rebuild’ option. This is more intensive to exchange so that is why you should do it during off-hours unless you have a small organization, in which case it won’t take that long.
Also, check the properties of your RUS. Is it running on the right server? What is the update interval? Is it using the correct Domain Controller?