I followed the breadcrumbs of your post (here and in the dedicated O365 forum).
Your initial issue (error 80004005-501-4B9-560 ) gets a few web search hits, all pointing at a defect in the MSFT Exchange datastore, (but apparently in older version of Exchange).
https://community.office365.com/en-us/f/158/t/294642
I'm not going to disagree with "Outlook could do a much better job handling this scenario, including not handing out a busted hyperlink, as it's not at all hard to redirect URLs..)
Anyway,
https://support.microsoft.com/en-us/kb/2637470
http://blogs.technet.com/b/eileenor/archive/2011/05/04/outlook-synchronization-error-80004005-501-4b9-560-with-a-microsoft-exchange-server-2010-mailbox.aspx
http://www.blog.edbtopst.org/resolve-error-code-80004005-501-4b9-560-while-synchronizing-outlook-with-the-exchange.html
All seem to confirm a server-side (or some kind of unexpected / unhandled blob-of-data-in-your-datastore) issue.
Assuming that you are exclusively using ExchangeOnLine, as part of Office365, (and are not using some form of hybrid/not-O365 additional mailbox/account), this looks to be something that MSFT O365 support would tackle for you, and not really a client-side
(Outlook) issue at all.
If your Office365 subscription is part of an organisational agreement, your in-house Office365 admin can raise a case with MSFT about this for you.
If your Office365 subscription is a personal subscription, I think you'll need to log a support case yourself directly. (which I think you can do back in the other forum/community).
(I'm not positive about the case-logging methods, because I'm not actually supporting Office365 for my organisation, at the moment, a project team is doing that, as we are still in early pilot tes