How to make Outlook search in server (not just locally-cached messages)

Solution 1:

Based on my knowledge, this behavior is up to your configuration in your outlook, the below screenshot for your reference:

If your Mail to keep offline setting is set to 12 months and you have email items in your Exchange mailbox that are older than 12 months, those items reside only in your mailbox on the server.

If you want to search all mails stored in exchange database, you could drag the Mail to keep offline slider to the desired number of months or to All to synchronize all email messages.

For more details: Only a subset of your Exchange mailbox items are synchronized in Outlook