The Issue
We recently had an issue where we tried to use the Conditional Access setting and only granting Terms of Use for an Android Device Enrollment.
The Investigation
What happens now is as described in our docs article Terms of use – Azure Active Directory | Microsoft Docs – The authenticator app installs…

Why is a problem? Well if your users have never set up MFA before, and they try to install MFA on their only device you have no *easy way of adding your user account (the other way is to log in on another device and go to myapps.microsoft.com and navigate to security and set up your security options where you can get the barcode.)
If you try to add an account you will get the below

and if I try add authenticator account I get the expected below result.

Where do I start my trobleshooting? By investigating the Conditional Access Policy first.

After not seeing anything too supsicious I also looked at the Company Portal on my Adnroid device again. And if you scroll down further I dicsovered some more information and an Advanced Diagnostics Button


I can also look under the Users and Sign-ins if I can see any errors, even on other user accounts I tested


But if I run a What-If under Devices – Conditional Access I can also see that my policy is the only one still applying. So it had to be something I was missing.

Some more reading in the initial Article Mentioned Above
What happens now is as described in our docs article Terms of use – Azure Active Directory | Microsoft Docs I came across this valuable piece of information,

The Solution
What more is the Company Portal than the Android Enrollment App? So I excluded it like so,

And Voila



I hope this post has been useful and as always please reach out to me if there are any corrections or contributions!