I had this problem for a while, but it seems, somehow, to have worked itself out (which is always worrying). To be more explicit: 

 - The problem started showing up, very suddenly, about two weeks ago. It affected my two macOS machines, one located at my institution, the other by broadband at home. I could get the messages fine via iOS or Outlook itself (standalone or web). 
 - Generally rebuilding immediately showed all new messages.
 - These problems were not fixed by completely removing the accounts and re-entering them (not just disabling and re-enabling them).
 - I did notice that, at least occasionally, even if I didn't rebuild, messages would sometimes show up several hours later.

However, over last weekend (a period when I logged into my machines less often than usual), messages started appearing in a more timely fashion. As of this week, things seem to be back to normal, at least for now.

Very curious, but at least it's working. OP @Christopher, do you have any updates?