How to salvage overgrown shared mailbox?

Hello,

What best practices would you recommend for a team to restructure their main shared inboxes?

There is a team at my company that uses two shared mailboxes (21 GB and 14 GB) that receive emails from multiple business groups. There are 50+ folders in each.

The search function in the Outlook app now refuses to even display results for the 21 GB mailbox. It works online though.

Search is now starting to be inconsistent for the 14 GB mailbox. Online it is unaffected.

The team hasn't been able to tell me if they can reduce the cache (i.e. only cache emails from the past week). They apparently need to constantly reference old emails.

My thought is that the team either needs to get used to Outlook online OR the mailbox owner needs to break up and restructure that one inbox into multiple streamlined inboxes.

Thoughts?