Я нашел.
ExchangeService service = new ExchangeService();
EmailMessage message = EmailMessage.Bind(new ItemId("someId"));
var alternateId = new AlternateId();
alternateId.UniqueId = message.Id.UniqueId;
alternateId.Mailbox = "somemailbox";
alternateId.Format = IdFormat.EwsId;
var convertedId = service.ConverId(alternateId, Format.OwaId) as AlternateId;
И преобразованный ID.UniqueId - это то, что мне нужно;