Ok, this was driving me insane and I looked on every blog and forum going, changed logging, made sure the time was syncing correctly as I know this causes an error too etc etc all to no avail.
There was one thing I hadn't tried though, on the Mac I had set up Mail with Exchange as well as Outlook. I had also set up contacts on Mac with Exchange so I could view the contacts for iMessage, as all of my contacts are on Exchange too and not iCloud.
I deleted the Exchange Account from the Mac completely apart from retaining the Outlook Exchange account which does not get deleted automatically being separate from the Mac Accounts.
It worked for me and has been fine since.
So if you have Exchange linked to other accounts on your Mac and not just Outlook, try removing them to see if it works.
Regards