C# – Can not delete meeting with exchange web services

We have a problem deleting Appointments from Exchange using EWS.

We try to delete Appointments from Exchange like this

ExchangeService service = new ExchangeService(ExchangeVersion.Exchange2007_SP1);
service.Credentials = CurrentUser; // NetworkCredential
service.Url = new Uri(WebserviceAddress);
service.UseDefaultCredentials = false;

var appointment = Appointment.Bind(service, id);
deletedAppointment.Delete(DeleteMode.MoveToDeletedItems, SendCancellationsMode.SendToAllAndSaveCopy);

We get an exception with the message "Object cannot be deleted."

Microsoft.Exchange.WebServices.Data.ServiceResponseException was
caught Message=Object cannot be deleted.
Source=Microsoft.Exchange.WebServices StackTrace:
at
Microsoft.Exchange.WebServices.Data.ServiceResponse.InternalThrowIfNecessary()
at
Microsoft.Exchange.WebServices.Data.MultiResponseServiceRequest1.Execute()
at
Microsoft.Exchange.WebServices.Data.ExchangeService.InternalDeleteItems(IEnumerable1
itemIds, DeleteMode deleteMode, Nullable1 sendCancellationsMode,
Nullable1 affectedTaskOccurrences, ServiceErrorHandling
errorHandling)
at
Microsoft.Exchange.WebServices.Data.ExchangeService.DeleteItem(ItemId
itemId, DeleteMode deleteMode, Nullable1 sendCancellationsMode,
Nullable1 affectedTaskOccurrences)
at
Microsoft.Exchange.WebServices.Data.Item.InternalDelete(DeleteMode
deleteMode, Nullable1 sendCancellationsMode, Nullable1
affectedTaskOccurrences)
at
Microsoft.Exchange.WebServices.Data.Appointment.Delete(DeleteMode
deleteMode, SendCancellationsMode sendCancellationsMode)
at
OurNameSpace.ExchangeCalendar.ViewCalendars.ExchangeMethods.DeleteMeeting(ItemId
id) InnerException:

If we instead try to use cancel the meeting

deletedAppointment.CancelMeeting();

we get an exception with the message "User must be an organizer for CancelCalendarItem action." This makes me really confused, because when I inspect the deletedAppointment object my email address is set as the organizer.

We create our meetings like this

Appointment appointment = new Appointment(service);
appointment.Subject = subject;
appointment.Body = body;
appointment.Start = start;
appointment.End = end;
appointment.Location = location;
appointment.RequiredAttendees.Add(location);
appointment.RequiredAttendees.Add(requiredAttendees);
try
{
    appointment.Save(SendInvitationsMode.SendOnlyToAll);
}
catch ...

location contains the name of a conference room mailbox.
if we pause a while (until the Appointment appears in Outlook) and call Delete on the same Appointment instance we used when we created the meeting the appointment is deleted successfully.

The code runs in a custom SharePoint 2010 WebPart. Not that I could think that it would make any difference, but who knows?

Why can't I delete the appointment?
How can I investigate further?
As far as I can see the code is mostly copy'n paste of an MSDN example.

Edit
When I copy a minimal example of the code to a Winform application the meeting is deleted correctly. Could there be any critical difference when running in the Sharepoint context?

Edit 2
CurrentUser is a user supplied username and password. The Exchange server is not on the same domain as SharePoint server.

Edit 3
If I open the appointment in outlook (with the same login as in the CurrentUser variable) I can cancel the appointment.