LDAP Bind was unsuccessful on directory OLDDC.domain.local for distinguished name ''. Directory returned error:[0x51] Server Down.
For more information, click http://www.microsoft.com/contentredirect.asp.
A domain controller had recently been demoted and Exchange was still pointing to it under "Recipient Update Services". Changing the specified DC in those settings resolved the issue.