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.
Also, FWIW (and for search purposes in the future), a few other bits of evidence for very similar problems over many macOS releases:
OP @Christopher, do you have any updates?