You seem to be experiencing the opposite of what most Outlook Gmail users face. Usually, there's a problem with duplicate sent messages.

This arises when the setting "save sent items in the following folder (Sent folder) on the server" is selected. Apparently, most email providers do not save a copy of an outgoing email into the IMAP sent folder when this setting is not selected. Gmail does so on its own. So users with that option enabled end up getting a duplicate.

When you say that your sent email cannot be found in the sent folder but can be found in the Gmail sent items, are you referring to the Outlook default PST sent folder or the IMAP sent folder for the gmail PST?

If it is the former, you can try selecting the dial button "Save sent items in the Sent items folder on this computer". Go to File> Account settings> Email> More Settings> Sent items.

Jay