This has been fixed on the v1.0.0 branch and can’t be backported to v0.16 without a schema migration, see IMAP SEARCH silently omits recently delivered messages when using an external SearchStore (eventual-consistency race)
Note that the UID SEARCH HEADER Message-ID "the-message-id" query won’t work until the index catches up. If that is an issue for Outlook, I suggest you report the problem to Microsoft as searching by message id for a message the client just created moments ago is both inefficient and error prone. IMAP is designed around UID, the message-id header is client defined and does not guarantee uniqueness.