I've been looking for a solution for a while for this. In our environment, this was caused by users selecting "Stay signed in to all your apps" on first login with Teams. Since the workstations are non-persistent, but the profile moves to each workstation, this caused 80070003 errors in Teams.
All solutions seemed to only be temporary - deleting app data would solve the issue, only for it to immediately return on next login. Teams is installed machine-wide, etc.
Solution:
- Get the user to sign out of their account in Settings > Accounts > Access work or school
- Apply the registry fix from Cozzy-0379 above:
Create registry entry to prevent users on RDS server from performing workplace AAD joins: HKLM\SOFTWARE\Policies\Microsoft\Windows\WorkplaceJoin, “BlockAADWorkplaceJoin”=dword:00000001
Step 1 works independently of step 2. Step 2 is just preventative. This is also a bit less destructive than wiping the whole profile. Users can also prevent this by clicking "No, sign in to this app only" when launching Teams for this time.