I am a developer that work on audio technologies for smartphone, so I have Android phones from every major phone maker, i.e., Samsung, Xiaomi, Moto, Google, etc... This issue happens with EVERYONE with them, so it's not a brand issue nor issue with the Bluetooth accessories. USB-C headset does not have this issue.
This issue started when Teams started to require "Nearby devices" permission for Bluetooth audio device late last year, just before this thread was created. I granted it access but it sporadically does not work - most times do not work. It used to work but the issue was introduced when the "Nearby devices" requirement was added.
Speaking purely from privacy concerns, Microsoft has NOT given us any valid reason why it needs "Nearby devices" access. Every other audio and VoIP app can support Bluetooth without such requirement. I guess Teams wants to use Bluetooth to scan nearby Teams Room audio devices but it creates the problem for everyone else, both in privacy concern and now that it doesn't seem to work... "Nearby devices" usually use BLE beacon function, so this is a form of location tracking of user... Serious security and privacy implications.
Please escalate this to your developer and fix this!!