I was trying to finish migrating to a new Exchange server, and was running both machines in parallel. Everything had been moved from the old server except for the Recipient Update Services. When I attempted to move one of the services to the new server, I received error code 0xC0070560, “The specified local group does not exist.” This error code conveniently does not exist in Microsoft’s knowledge base.
Apparently during some other server and Active Directory moves, the Exchange Enterprise Servers group in the Users OU of the root domain was changed to a Universal security group. After changing the Exchange Enterprise Servers group back to Domain Local, I was able to point the recipient policy at the new server and proceed with the uninstall on the old server.