Mails sent FROM an external sender do not appear in search

Hi there, 

We have shared mailboxes, and on one of our shared mailboxes, any email sent FROM an external sender does not appear in any search criteria. 

I have checked if these mails appear anywhere, and they can be searched for successfully in webmail.

I don't want to go down the route of mapping the mailbox as a second account, because I find that when I do that, weird things start happening with the outbox. Sometimes, mails are sent, sometimes they are not. Some users see more mails in their inbox than others who are using the same shared mailbox. 

I have also tried recreating a new profile, but the search function still does not show mails sent from an external sender.