I have some users getting this error and some not receiving any email from external resources. I recently had to restage the server hosting these records and have since then brought it back online with the same records. Did this in any way effect the existing recipient policies or other exchange settings that govern how mail was being received by internal users?