To keep the discussion alive and to "entertain" everyone ab bit:
In all of my pain, I decided to change my mailbox plan towards a so called business mailbox, hosted on OpenXChange for 4,95€ per month, hoping to use OpenXChange to become a substitute of iCloud. Actually OpenXChange can handle Calendar, Contact and Tasksync with Outlook and is being widely used at Email-Providers, at least in Germany.
Guess what, that Outlook Connector is not working with Outlook 2016:-( A subsequent inquiry to my Provider 1&1 (who nowadays offer fast and excellent support) revealed, that "OpenXchange is hard working on Outlook 2016 compatibility, but Outlook 2016 being pretty new"...
So also Microsoft may/must have changed something deeper, but one should expect from Apple that 6 month should be enough to investigate and deliver a solution.
I am now thinking of upgrading my Email even further to hosted MS Exchange. This should be compatible to Outlook by all means, shouldn't it? ;-)