A small number of clients can't sync their postbox with exchange (2013). When they try to do it outlook (2016) will throw an 0x8004010F error saying that it "Can't find Object" but doesn't say which object. In fact there is no communication with the server at all. Using wireshark I did find out that outook is trying to resolve the SRV Entry for _autodiscover._tcp.domainname.xyz which succeeds but even with that information no communication happens at all. The same clients can download their mails through POP3 or IMAP without any problem at all. So it seems to be some kind of MAPI issue.
I tried all kinds of things but nothing seems to work. I did try to fix the .ost file. (Which wasn't corrupt). I did create new profiles, did a repair installation of office and did follow the microsoft documentation regarding that failure. (which seemed to focus more on this version of the error which regards the missing local file).
// These problems seem to be tied to specific hosts. The affected users are able to use their accounts on other hosts.