Hi @Chris Helms,
According to your description, I tested it in my environment. If the shared mailbox is added via automapping, the records can only be searched by clicking on shared mailbox and selecting "current folder"; and if we use “All mailboxes” no result are returned. This is a design limit.
To work around this issue, you can add the Shared Mailbox as a secondary Exchange account to the profile. First you will need to check if the shared mailbox is already listed as an account in the profile. If so, you will have to remove it. You could refer to Troubleshooting Outlook search issues - Microsoft Support for more information.