Finally I found the issue. I uninstalled MS Teams completely on the work profile and installed the latest version from Play store on the private profile.
And IT WORKS!
So it must be an issue caused by the version managed by the organization.
Uninstalling and re-installing seems to help temporarily - and sometimes.
My issues started last week (as others), and yesterday I was able to fix it by uninstalling and re-installing. It worked for couple of hours, until I ran to the same issue yet again. I tried the uninstalling and re-installing, twice or thrice actually, and no luck. BT headset didn't work. All installations were from Play store using the private profile.
Inspired by your post I decided to do it once more, and this time it worked. Nothing else changed, except perhaps the first login was done with different profile than earlier today. Now it works again, and I am able to switch between all three different teams accounts which I have and the BT works fine.
Btw, my setup is quite identical as yours, a bit older OnePlus (7 Pro) but same headset. Also in another thread about this issue there are couple persons having OnePlus.