Searching Outlook contacts synchronised to Teams on a Poly Teams handset

Over the last 4 weeks, we have had dozens of issues after we upgraded our onsite phone system to Microsoft Teams calling plan and using Poly CCX500 handsets, we also tried other handsets from other manufacturers and they all have the same issue as well, and we are struggling to even log a job with Microsoft support in regards to this issue with us getting sent around the houses.

The problem we have is that we can't search Outlook contacts that are synchronised over to the Teams software installed on any Teams based deskphone, you can search via the company directory fine and you can see the Outlook contacts in a random order at the bottom of the company directory but you can't search for any contact that was synced from Outlook.

Anyone have any ideas at all please?  The response from Poly, as well as the other handset manufacturers we have spoken to, including Yealink, is that the issue is the Teams software on the phone and not their handset and Teams will overwrite any and all settings on the handsets themselves so they are powerless to do anything and to talk to Microsoft.