Symptoms
Workflow notifications do not send to some users. In the HostServer log, the error "Provider did not return a result for K2::DOMAIN]]USER] on GetUser" is logged for the users in question.
Diagnoses
The K2 service account did not have the correct permissions on the OU containing the group.
Resolution
Granted access to the K2 service account, and once those changes had replicated across the environment, the user resolved correctly.