Why does mail sync with Outlook not work?

I followed your advice, completely removed the Exchange account from my MacBook Air, and then added it again in Mail.

The good news: It worked without problems, and my Inbox now is complete again. Strangely, while I had to agree that the Exchange account would be removed from ALL my Macs, when I restarted my MacBook Pro (which was shut down during this operation), everything was in place as before - no need to re-add the account there. Fine by me, but somewhat disconcerting if things don't behave as expected.

The bad news: While the Inbox has been fully restored, one of the other mailboxes of that account has disappeared entirely (the first out of 39), without any rhyme nor reason. Everything else seems to be in place, but this is decidedly odd. (I found a workaround, but only by moving the content of that mailbox on my MacBook Pro, where it was untouched, to a different mailbox).

In summary - it seems I'm o.k. for now, but I continue to be concerned by odd behavior. I would suggest that Mail in Catalina needs a bug-fix upgrade!

Thank you for helping me with this - much appreciated. First off, I re-checked and, yes, my software is fully up-to-date. I then followed your advice to set up a new user (I had to laugh when I followed your link as the page was in Korean or some other script unknown to me, but I know anyway how to do this). I set up Mail with my MS Exchange account (sorry, of course it's EXCHANGE, not "Outlook" as I incorrectly wrote earlier), and lo and behold, everything showed up as it should. I did a couple tests - it appears (so far) as if Mail for this new user does indeed synchronize this account nicely with whatever I do on my other Mac.

On point that may be relevant is that I did NOT enable my AppleID when I set up that new account. My standard account does have Apple ID enabled, and when I tried to remove the Exchange account to see if I can set it up from scratch, I was only given the option to "disable" it on my MacBook Air or delete it simultaneously on ALL my devices (including iPhone). Of course I didn't dare choose the latter, so I chose "disable" which simply made the account greyed-out in the Internet Accounts listing in System Preferences, but not disappear. When I then tried to "add account" in Mail, it would recognize that the account already existed and only gave me the option to re-enable Mail, Contacts etc.. I did that, and ALL of the previously visible mailboxes appeared again, with the EXACT same content (including with everything from before yesterday still missing from my Inbox, while it's still there on all other devices, in Outlook and in my new user account on the MacBook Air). So I am wondering whether there is some conflict between AppleID/iCloud and setting up an account cleanly.

This sounds really scary. This is my main work email - right now it works just fine on my MacBook Pro, my iPhone, and on the "other user" on my MacBook Air. Can you guarantee that by removing it from ALL of these devices, I won't end up loosing a bunch of older emails from my Inbox as happened on my main account on the MacBook Air? (For what it's worth, it is still eternally spinning "Moving Messages 1 of 22"...)

Not to mention the work required to set it up again everywhere...

Thanks again. I understand what you are saying. I just was hoping that there might be a work-around (e.g., temporarily disabling my iCloud account on my MacBook Air) that would allow me to delete the Exchange account ONLY on that computer, and not all my devices at once.

Here is an update on my Mail issues: While it worked for a while, Mail on my MacBook Air (running Catalina) and my MacBook Pro (running Mojave) have once again fallen out of sync. In particular, any action I perform on one of my Exchange mails on my Air (e.g., delete) is not reflected on the actual Exchange account or the MacBook Pro. And once again, the persistent message pops up on my Air in the bottom left corner of Mail, saying "Moving Messages 1 of 10" forever without a change. So much to my regret, I'm pretty much back to where I was when I sent out my initial request for help. Can anybody tell me what else I could try? What is the Mac actually DOING while it incessantly displays this "Moving..." message?