I was able to connect to EWS referencing the Microsoft.Exchange.WebServices.dll and it works fine when debugging the Store app in Visual Studio.
ExchangeService service = new ExchangeService(ExchangeVersion.Exchange2007_SP1);
service.Url = new Uri("https://OURSERVER/EWS/Exchange.asmx");
service.UseDefaultCredentials = true;
service.Timeout = 12000;
EmailMessage message = new EmailMessage(service);
message.ToRecipients.Add("something@something");
byte[] screenshot = await ImageToByteArrayAsync(bitmapStream);
message.Attachments.AddFileAttachment("screenshot.bmp", screenshot);
message.Body = "stuff";
message.SendAndSaveCopy();
Unfortunately, when you run the deployed application it throws an exception reporting "Unable to load resources for resource file Microsoft.Exchange.WebServices.Strings in package".