Scott Duffey as per mdaiber response. This is the exact issue I was having with bulk enrolled devices that were hybrid Azure AD joined and then enrolled into Intune with the GPO policy. On opening the Company Portal application it reports the device is not enrolled into Intune and then prompts to enrol (the machine is most definitely enrolled).
On adding the app registration with the redirect to the AAD.Broker services for the Company Portal the issue was instantly resolved and SSSO now also works absolutely perfectly. On checking some other tenants I manage that don't have the issue they have a "Microsoft Intune" Enterprise application present that is not in the problem tenant, so there may be an internal deployment issue going on with Azure/Intune.
I'm based in Brisbane, if you want to go into further detail send me a message and I'd be happy to jump on a call and go over my findings if you want.