Outlook with Exchange 2013 not working

Hi, We have Exchange 2013 and using Outlook 2019. 

In OWA we can search all emails with no issues.

For all users in Outlook it only shows the most recent emails when we attempt to search and sits and spins when looking at older emails that are "stored" on the Exchange server.

I have rebuilt the personal OST/PST files on user computers and get the same results.

"Get-MailboxDatabaseCopyStatus" Shows that the database is Mounted and Healthy.

What else can I attempt to remedy this?