After a long search and dozens of tests I seem to have found my problem:
First of all, WebDav does NOT work with Exchange Online.
There is a solution using WebServices, that works quite nice.
I seem to have to set the Exchange Version to 2007_SP1. I did not find any option to leave this item blank or have it detected.
var service = new ExchangeService(ExchangeVersion.Exchange2007_SP1);
// Just to get the trace messages
service.TraceEnabled = true;
ServicePointManager.ServerCertificateValidationCallback = CertificateValidationCallBack;
service.UseDefaultCredentials = false;
service.Credentials = new WebCredentials("<Username>", "<Password>");
// Autodiscover does NOT work if Exchange is not in the local net
// This is the url you have to use for german account (red002)
service.Url = new Uri("https://red002.mail.emea.microsoftonline.com/ews/Exchange.asmx");
What I still cannot understand is why you have to know the exchange version in advance, and have no option to negotiate that with a call.
Similar is the fact that I have to know the URL to be able to connect to the exchange server. Is it not the basic idea of the cloud to NOT have to know where your data is hosted?
I hope this code helps somebody. I sure would have needed this advice :-)