I suspect that the search is broken because it relies on the exchange bits to find users.

Did search _ever_ work, though?

From the Health Status page:

"Microsoft Teams: Most of the core functionality including joining calls, meetings, group chats, and channel messages are not impacted. Scenarios that depend on Exchange Online, including Calendar related failures with scheduling, invites, viewing, and meeting edits. Creation of Live or Virtual events fail. Failures with Copilot responses for outlook, calendar, or M365 files, read history, or adding to new chats. Navigating to App chats, adding new contacts or syncing contacts in settings fail. Standard channels are working fine but users may experience the inability to create or delete private or shared channels."

Teams relies on Exchange API to autocomplete your search for colleagues, if you know someone's full email you should be able to start it that way.