I would do a quick rebuild of the recipient update services in Exchange manager and verify they are updating by building a test account and trying to send mail.