The DEP process should take effect prior to the Setup Assistant prompt to restore from backup. Do you have supervision enabled as part of the device management settings for the DEP profile? It is required for devices using Company Portal as the authentication method. Other things to check would be the number of available licenses for Company Portal. Hope this helps.
@trebelow Well, this is an issue that definitely exists and I am able to reproduce.
A small subset of our users are permitted to have a relatively relaxed configuration which includes allowing backup/restore to/from iCloud. On such devices the Remote Management screen appears during device setup and the DEP profile appears to be downloaded to the device. However, I suspect the subsequent restore from iCloud breaks this as, the Company Portal and Authenticator apps are never delivered by Intune via DEP+VPP. In the enrollment portal, the device is listed as in a state of "Not Contacted." Certain DEP device features such as locked enrollment, are not enforced.
(Starting again and setting up the device as a new device, results in expected behaviour.)
For the restored devices, as a workaround we are able to download Company Portal via app store and enrol as a personal iOS device, then switch the device type to Corporate later on. However as stated above, the device is not fully DEP-enrolled.