How very stupid of me. I forgot to impersonate. Since I'm calling into EWS with a service account it is of course listening on the mailbox of that account unless you specify:
_service.ImpersonatedUserId = new ImpersonatedUserId(ConnectingIdType.SmtpAddress, _primaryLabUserId);