Issue was that accounts using these devices did not had Intune license as part of Office 365 E3. This was resolved by purchasing Enterprise Mobility + Security E3 (or E5), then all these devices will auto enroll into intune as Corporate. Then admin can change into Private if needed.
So unless devices are enrolled by DEM account, for Out Of Box Experience, in order for devices to be properly enrolled, the user accounts must have Intune license as part of office packages.