Discrepancy between Outlook and Gmail Mailbox

Bumped into an interesting problem over the last couple of days: I have a client who has a Gmail account that they inexplicably want to use with Outlook. They do a lot of mail sorting, and we started seeing issues with messages which appeared incorrectly in Outlook. When checking on Gmail in the web interface, we have messages which are missing that appear in Outlook. This is the case both for Outlook desktop, and the Outlook mobile apps. Those match up, and Gmail apps match up. I tried adding the accounts as IMAP, and they accurately reflect what Google is showing us in the web interface.

Do I recall correctly that Microsoft caches Gmail to feed to Outlook when you log in as a Gmail account? If so, it seems like the cache is messed up, and I don’t have a solution to that other than “just log on with IMAP,” which isn’t ideal but at least correctly reflects the data in the Gmail mailbox. Anyone seen this before? Any way to get Microsoft to rebuild the cache they keep?

It’s.. it’s really bad to have a user believe they have email saved in one folder and it turns out that it’s not there at all.