Maybe it only does this once and if you have removed Teams it is not trying to install it again? Or maybe this only happens for new users?
No. As I know, only MSI-based installer will be installed when a user signs into a new Windows User Profile.
After you applied the new GPO, you should restart the client machine or run gpupdate /force to take effect. Meanwhile, make sure you are installing or updating to Version 1905 or later of Microsoft 365 Apps.
If the response is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.